Hướng dẫn cho Kaninho cùng người bạn Henry


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: cuom1999

Bài toán có thể mô hình lại như sau: Hai bạn chơi một trò chơi có \(n\) viên đá. Ở mỗi thao tác nếu trên bàn có nhiều hơn \(k\) viên đá, bạn được bốc ra một số viên đá sao cho trên bàn còn tối thiểu \(k\) viên. Nếu trên bàn có không quá \(k\) viên đá thì phải bốc đúng 1 viên. Ai không bốc được nữa thì thua cuộc. Hỏi ai là người thắng?

Đến đây, chúng ta có thể thấy người đi trước có rất nhiều lợi thế. Để ý rằng nếu số viên đá còn lại là \(k\) hoặc \(k + 1\) thì những lượt tiếp theo, mỗi người đều phải bốc đúng 1 viên. Như vậy nếu ban đầu có nhiều hơn \(k + 1\) viên đá thì người đầu tiên có quyền bốc sao cho số đá còn lại là \(k\) hoặc \(k + 1\) dựa theo tính chẵn lẻ của \(k\) và chiến thắng. Trường hợp ban đầu không quá \(k + 1\) viên có thể được xử lý bằng tay.



Bình luận

Không có bình luận nào.