Tắt đèn
Đề bài
Mô tả
Một buổi tối, Bash và Chikapu đến một tòa chung cư bỏ hoang có tầng. Thật bất ngờ, ở mỗi tầng vẫn còn một số bóng đèn hoạt động! Hai bạn chạy lên chạy xuống, bật tắt thử các bóng đèn và thấy rằng ở tầng thứ có bóng đèn còn hoạt động. Ở mỗi tầng, các bóng đèn được đánh số từ đến theo thứ tự từ trái sang phải.
Hiện tại hai bạn đang đứng trên sân thượng, sau khi đã tắt hết các bóng đèn ở mỗi tầng, trừ bóng đèn ngoài cùng bên phải (bóng số , bóng cần dùng để đi cầu thang).
Vốn hiếu thắng, hai bạn nghĩ ra trò chơi sau. Hai người chơi lần lượt thay phiên nhau, Bash đi trước. Ở mỗi lượt:
- Người chơi chọn một số và đi đến tầng thứ .
- Người chơi chọn một bóng đèn đang bật ở tầng thứ .
- Người chơi tắt bóng đèn , đồng thời đảo trạng thái (bật thành tắt, tắt thành bật) của không, một hoặc hai bóng đèn tùy ý cùng tầng nằm bên trái bóng .
Trò chơi kết thúc khi tất cả bóng đèn đều tắt; người thực hiện lượt cuối cùng là người thắng. Hãy xác định người thắng nếu cả hai đều chơi tối ưu. Nếu Bash (người đi trước) thắng, hãy đếm số nước đi đầu tiên khác nhau mà sau đó Bash chắc chắn thắng, lấy theo modulo .
Hai nước đi được coi là khác nhau nếu:
- tầng được chọn khác nhau, hoặc
- bóng đèn được chọn khác nhau, hoặc
- tập các bóng đèn bị đảo trạng thái khác nhau.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên (): số bộ test. Mỗi bộ test gồm:
- Dòng đầu tiên chứa số nguyên (): số tầng.
- Dòng thứ hai chứa số nguyên (): số bóng đèn ở mỗi tầng.
Tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in kết quả trên một dòng:
- Nếu Chikapu thắng, in
Chikapu. - Nếu Bash thắng, in
Bashrồi một dấu cách và số nguyên : số nước đi đầu tiên sau đó Bash chắc chắn thắng, lấy theo modulo .
Ràng buộc
- , tổng trên tất cả các bộ test không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 2 1 4 1 2 3 4 |
Bash 1 Chikapu |
Ví dụ của đề gốc. |
| 4 1 5 2 2 3 3 3 6 7 2 4 4 |
Bash 1 Bash 1 Bash 3 Chikapu |
Ví dụ bổ sung, tính bằng lời giải mẫu. Bộ test thứ nhất: nước thắng duy nhất là tắt bóng và không đảo bóng nào, khi đó mọi bóng đều tắt. Bộ test cuối: hai tầng giống hệt nhau, Chikapu chỉ cần lặp lại nước đi của Bash ở tầng còn lại. |
Bình luận