Đàn bò hỗn loạn

View as PDF

Submit solution


Points: 0.18 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO November 2008
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mỗi cô trong ~N~ cô bò ~(4 \le N \le 16)~ của bác John đều có một số seri phân biệt ~S_i~ ~(1 \le S_i \le 25{,}000)~. Các cô bò tự hào đến nỗi mỗi cô đều đeo một chiếc vòng vàng có khắc số seri của mình trên cổ theo kiểu các băng đảng giang hồ.

Các cô bò giang hồ này thích nổi loạn nên đứng xếp hàng chờ vắt sữa theo một thứ tự được gọi là "hỗn loạn".

Một thứ tự bò là "hỗn loạn" nếu trong dãy số seri tạo bởi hàng bò, hai số liên tiếp khác biệt nhau nhiều hơn ~K~ ~(1 \le K \le 3400)~. Ví dụ, nếu ~N = 6~ và ~K = 1~ thì ~1~, ~3~, ~5~, ~2~, ~6~, ~4~ là một thứ tự "hỗn loạn" nhưng ~1~, ~3~, ~6~, ~5~, ~2~, ~4~ thì không (vì hai số liên tiếp ~5~ và ~6~ chỉ chênh lệch ~1~).

Hỏi có bao nhiêu cách khác nhau để ~N~ cô bò sắp thành thứ tự "hỗn loạn"?

Input

  • Dòng ~1~: Hai số ~N~ và ~K~ cách nhau bởi khoảng trắng.
  • Dòng ~2..N+1~: Dòng ~i+1~ chứa một số nguyên duy nhất là số seri của cô bò thứ ~i~: ~S_i~

Output

Một số nguyên duy nhất là số cách để ~N~ cô bò sắp thành thứ tự "hỗn loạn". Kết quả đảm bảo nằm trong phạm vi kiểu số nguyên 64-bit.

Sample Input

4 1
3
4
2
1

Sample Output

2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.