Đàn bò hỗn loạn

View as PDF
Submit solution
Points: 0.06 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
USACO November 2008
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.


  • -10
    phannam310810  commented on June 4, 2025, 12:46 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -2
    quan0802010  commented on Dec. 30, 2024, 3:09 p.m. ← edited

    dasdasdsa


  • 0
    ijk  commented on Dec. 29, 2024, 5:00 p.m.

    Có cách nào tối ưu hơn quay lui không ah, em bị TLE 3 test cuối mãi


    • 2
      chidang  commented on Feb. 1, 2025, 2:26 a.m.

      dp bitmask


  • 2
    chunguyen2k8  commented on March 27, 2024, 3:05 p.m.

    Bài hay quá :3