Thắng hay đóng băng
Đề bài
Mô tả
Hai người chơi một trò chơi với một số nguyên ban đầu được viết trên giấy. Đến lượt mình, người chơi phải viết một ước không tầm thường của số được viết gần nhất, tức là một ước khác và khác chính số đó.
Người nào không thể đi tiếp thì thắng cuộc. Hãy xác định xem ai sẽ thắng nếu cả hai chơi tối ưu. Nếu người đi đầu thắng, hãy in ra một nước đi đầu tiên hợp lệ của họ.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên .
Dữ liệu ra
In ra số thứ tự của người thắng (1 hoặc 2).
Nếu người đi đầu thắng, dòng thứ hai in ra nước đi đầu tiên của họ — một ước không tầm thường của sao cho sau nước đi này người thứ hai chắc chắn thua. Nếu người đi đầu thắng mà không thể đi nước nào (tức không có ước không tầm thường), in ra .
Nếu có nhiều nước đi hợp lệ, in ra bất kỳ nước nào.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 | 2 | chỉ có hai ước không tầm thường là và . Sau khi viết hoặc , đối thủ không đi được nữa nên đối thủ thắng. Vậy người đi đầu thua, người thứ hai thắng. |
| 30 | 1 6 |
Người đi đầu viết — số là số mà người đi sau gặp phải sẽ thua (như ví dụ trên). |
| 1 | 1 0 |
Số không có ước không tầm thường nên người đi đầu không đi được, do đó thắng luôn. |
Bình luận