Trò chơi Síp
Đề bài
Mô tả
Cường và Mai đang chơi một trò chơi với các con số, có nguồn gốc từ Síp, một quốc gia nhỏ ở châu Âu. Trò chơi bắt đầu với một cặp số nguyên dương . Hai người lần lượt biến đổi cặp số này, Cường đi trước. Ở mỗi lượt, người chơi có thể thực hiện một trong các nước đi sau:
- Nếu chẵn: ;
- Nếu chẵn: .
Trò chơi có kết cục:
- Nếu trò chơi đến một trạng thái mà cả và đều lẻ, người đến lượt không có nước đi hợp lệ và thua cuộc.
- Nếu trò chơi đến một trạng thái đã từng xuất hiện trước đó, trò chơi kết thúc với kết quả hòa.
Giả sử cả Cường và Mai đều chơi tối ưu. Cho , hãy đếm số trạng thái bắt đầu với mà trò chơi kết thúc theo mỗi kết cục trong kết cục.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên ().
Dữ liệu ra
In ra số nguyên trên dòng:
- Số trạng thái bắt đầu mà Cường thắng;
- Số trạng thái bắt đầu dẫn đến kết quả hòa;
- Số trạng thái bắt đầu mà Mai thắng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 | 1 2 1 |
Có trạng thái bắt đầu. : Cường không có nước đi, Mai thắng. : Cường chỉ có một nước đi đến , rồi Mai chỉ có một nước đi đến , trò chơi hòa. : tương tự trạng thái trước. : Cường có hai nước đi đến hoặc , cả hai trường hợp Mai đều không còn nước đi, Cường thắng. |
| 3 | 1 4 4 |
Ví dụ bổ sung (không có trong đề gốc). Cường chỉ thắng ở . Hòa ở , , , . Mai thắng ở , , , . |
Bình luận