Thành phố nơi bạn sống nằm bên bờ dòng sông Binary kỳ vĩ. Nước sông đến từ một số phụ lưu bắt nguồn tận trên núi. Không may cho thành phố, những người nông dân sống trên núi cần dùng một phần nước trong các phụ lưu để tưới cây.

Từ lâu, thành phố đã thỏa thuận cho nông dân canh tác mà vẫn duy trì dòng sông: mỗi nông dân được dùng nước cho ruộng đúng một nửa thời gian. Họ luân phiên chuyển nước vào ruộng trong một ngày rồi để nước chảy xuống sông trong một ngày. Kết quả lại là thảm họa! Vì việc dùng nước của tất cả nông dân đồng bộ, ai cũng cùng chuyển nước hoặc cùng không chuyển nước, nên cứ một ngày sông lại cạn, ngày kế tiếp thành phố lại ngập lụt.

Để giải quyết vấn đề, thành phố yêu cầu mỗi nông dân chọn một lũy thừa nguyên nào đó của 2 (dù sao đây cũng là sông Binary) trong đoạn từ 1 đến \(D\), rồi cứ mỗi khi số ngày ấy trôi qua lại đổi trạng thái sử dụng nước: bắt đầu hoặc dừng lấy nước. Không nhất thiết mọi lũy thừa của 2 từ 1 đến \(D\) đều được chọn, và nhiều nông dân có thể chọn cùng một số. Số 1 cũng được tính là một lũy thừa của 2. Ý tưởng là làm tổng lượng nước sử dụng đều hơn để hạn hán và lũ lụt ít xảy ra hơn.

Chuyện đó đã diễn ra từ lâu. Gần đây, bạn và những người dân khác bắt đầu nghi ngờ rằng nông dân không tuân thủ thỏa thuận; thậm chí bạn còn không biết hiện có bao nhiêu nông dân. Dữ liệu duy nhất là lịch sử lưu lượng nước qua thành phố trong \(N\) ngày. Bạn có thể xác định họ có trung thực không?

Mỗi phụ lưu có lưu lượng 1, và lưu lượng sông chính bằng tổng lưu lượng của mọi phụ lưu không bị chuyển nước sang ruộng. Trước khi xem bản ghi, bạn không biết có bao nhiêu phụ lưu. Mỗi phụ lưu bị nhiều nhất một nông dân chuyển nước, nhưng có thể có những phụ lưu không bao giờ bị ai chuyển nước. Các chu kỳ chuyển nước đã bắt đầu từ rất lâu trước khi thành phố ghi nhận lưu lượng, và không có gì bảo đảm chúng cùng bắt đầu vào một ngày.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(N\), \(D\) cách nhau bởi dấu cách. Dòng tiếp theo chứa \(N\) số nguyên; số thứ \(i\), ký hiệu \(d_i\), là lưu lượng sông trong ngày thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: M, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(M\) là số nông dân nhỏ nhất có thể đang chuyển nước khỏi các phụ lưu theo đúng mô hình đã mô tả và phù hợp với lưu lượng quan sát được.

Nếu chắc chắn có ít nhất một nông dân đang hoạt động nhưng dữ liệu đã cho không thể được giải thích bởi các nông dân tuân thủ quy tắc, in CHEATERS! thay cho một số.

Ràng buộc

• \(1\le T\le50\).
• \(D\) là một lũy thừa của 2.
• \(1\le D\le\lfloor N/2\rfloor\).

Phân nhóm

• Tập nhỏ: \(1\le N\le50\); \(0\le d_i\le5\).
• Tập lớn: \(1\le N\le5000\); \(0\le d_i\le1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
5 2
2 2 2 2 2
6 2
1 1 1 0 0 0
8 4
2 1 1 0 0 1 1 2
8 4
0 1 1 3 1 2 2 2

Case #1: 0
Case #2: CHEATERS!
Case #3: 2
Case #4: 3

Nguồn

Google Code Jam 2015, Vòng 3, bài River Flow.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.