Bốc trứng
Xem PDF
Điểm:
180
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bốc trứng là một trò chơi trí tuệ cổ điển ở Việt Nam. Trong trò chơi này bạn và một người khác sẽ lần lượt thay lượt chơi, khi trò chơi bắt đầu trên màn hình sẽ hiện ra \(n\) quả trứng, mỗi lượt bạn hoặc một người khác được chọn một số trứng bất kì từ \(1\) đến \(k\) và xóa khỏi màn hình, người xóa được quả trứng cuối cùng là người thắng cuộc.
Hôm nay Rùa đến nhà ngài Thỏ để thách đấu với ngài ấy về trò chơi này. Bạn hãy giúp Rùa thắng ngài Thỏ nhé!
Input
- Dòng thứ nhất chứa số \(T(1 ≤ T ≤ 100000)\) - Thể hiện số lượng ván đấu
- T dòng tiếp theo, mỗi dòng chứa 2 số nguyên n, k. \((1 \le k \le n \le 10^{18})\)
Output
- In ra \(T\) dòng, ứng với ván đấu thứ \(i\), in ra "Rua Win" nếu Rùa thắng và in ra "Tho Win" nếu ngược lại (giả sử Rùa đi trước và mỗi người đều chơi tối ưu).
Example
Test 1
Input
2
4 2
10 4Output
Rua Win
Tho Win
Bình luận
Em mới ra ngoài xem thử Lý thuyết trò chơi xong vẫn không biết gì ;-;
-
4
huyhau6a2
9:22 p.m. 17 Tháng 8, 2022
←
đã chỉnh sửa
→
- Nếu số lượng trứng <=k ngay ban đầu thì Rùa Win(nhưng ta có k<=n nên trường hợp không xảy ra)
- Số lượng trứng =k+1 thì Rùa sẽ có bất lợi lớn vì bốc bao nhiêu cũng sẽ có cách cho Thỏ Win. Trừ khi thỏ sai lầm nhưng ở đây ghi cả 2 đều chơi tối ưu nên đáp án là Thỏ Win
- Vì thế, với các số trong đoạn k+2 đến 2k+1 thì Rùa sẽ làm cho số lượng trứng =k+1 để đưa thỏ vào thế bất lợi. Vì thế Rùa Win
- Ta có kết luận như sau:
- Giả sử n%(k+1)=0 thì Thỏ Win, vì trong lượt cách chơi tối ưu của thỏ sẽ làm mất k+1 trứng mỗi lượt đưa rùa vào thế bất lợi
- Ngược lại thì rùa sẽ làm cho số trứng chia hết cho k+1 để đưa thỏ vào thế bất lợi. Vì thế Rùa Win
-
1
trieunguyen_a1
3:45 p.m. 22 Tháng 8, 2022
2 bình luận nữahttps://vnoi.info/wiki/algo/math/game-theory.md. Bạn có thể đọc bài viết này với bài toán trò chơi bốc sỏi cơ bản.
Nếu bạn muốn lời giải chi tiết thì mình cũng xin phép được nói:
Nếu bạn có vấn đề gì hãy comment cho mình nha
thanhs anh