Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11PF - Dãy số hoàn hảo

Dãy số A gồm n số nguyên khác nhau từng đôi: a1, a2, ..., an được gọi là hoàn hảo nếu như nó thỏa mãn tính chất sau: "Không tồn tại 3 chỉ số p < q < r sao cho hoặc ap < aq < ar hoặc ap < ar < aq hoặc aq < ap < ar".

Cho A là dãy hoàn hảo, một phép chèn một số nguyên b vào dãy A để tạo thành dãy B (b có thể được chèn vào trước a1, hoặc giữa ai, ai+1 với 1 ≤ i < n, hoặc sau an) được gọi là hợp lệ nếu như các điều kiện sau được thỏa mãn:

  • b > ai với mọi 1 ≤ i ≤ n
  • Dãy B là hoàn hảo

Yêu cầu

  • Hãy tính số lượng phép chèn hợp lệ một số b vào dãy A.
  • Giả sử B là một dãy thu được bởi một phép chèn hợp lệ b vào A. Hãy tính số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của B.

Dữ liệu

  • Dòng thứ nhất chứa hai số nguyên n và b tương ứng với số lượng phần tử của dãy A và số nguyên cần chèn. Biết rằng 3 ≤ n ≤ 105, |b| ≤ 106.
  • Dòng thứ hai chứa n số nguyên a1, a2, ..., an, mỗi số có trị tuyệt đối ≤ 106.
  • Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả

  • Dòng thứ nhất ghi một số nguyên là số phép chèn hợp lệ số b vào dãy A.
  • Dòng thứ hai ghi một số nguyên là phần dư trong phép chia cho 109 của số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của dãy B. Nếu không thể chèn được b vào dãy A, ta ghi ra 0.

Ví dụ

Input:
4 2012
55 25 9 20 Output: 2
8

Giới hạn

Có 50% số test có n ≤ 15.


Được gửi lên bởi:Quan To
Ngày:2012-08-22
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED

hide comments
2016-11-02 16:31:34
Code pascal:
http://shink.in/XmdWe
2015-12-10 14:37:48
cho em hoi sao ma em co 90 diem vay,may anh co biet chi em vs

2014-08-10 06:12:09 Kakabalo
nếu ko chèn dk thì in ra mấy số 0 vậy @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.