Change background image
Chuyên Tin - Lê Khiết

Go downThông điệp [Trang 1 trong tổng số 1 trang]

© FMvi.vn

on Sat Dec 22, 2012 10:37 pm
Admin
avatar
avatar

Code - Huyền Thoại

12028. Dãy số hoàn hảo

Mã bài: C11PF
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.
http://chuyentinlk.123.st

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Admin
Trả lời nhanh

Về Đầu TrangThông điệp [Trang 1 trong tổng số 1 trang]

  © FMvi.vn

|_-Diễn Đàn Tin Học - Lê Khiết-_|

« Xem bài trước | Xem bài kế tiếp »

Bài viết liên quan

    Quyền hạn của bạn:

    Bạn không có quyền trả lời bài viết