题解报告:hdu 4764 Stone(巴什博弈)

时间:2021-06-11 13:41:58

Problem Description

Tang and Jiang are good friends. To decide whose treat it is for dinner, they are playing a game. Specifically, Tang and Jiang will alternatively write numbers (integers) on a white board. Tang writes first, then Jiang, then again Tang, etc... Moreover, assuming that the number written in the previous round is X, the next person who plays should write a number Y such that 1 <= Y - X <= k. The person who writes a number no smaller than N first will lose the game. Note that in the first round, Tang can write a number only within range [1, k] (both inclusive). You can assume that Tang and Jiang will always be playing optimally, as they are both very smart students.
唐和江是好朋友。为了决定吃晚餐的人,他们正在玩游戏。具体来说,唐和江会在白板上写数字(整数)。唐先写,然后写江,然后再写唐,等等......此外,假设前一轮写的数字是X,下一个玩的人应该写一个数Y,使得1 <= Y - X <= k 。首先写入不小于N的数字的人将失去游戏。请注意,在第一轮中,唐可以只在范围[1,k](包括两端)内编写一个数字。你可以认为唐和姜总是会打得最好,因为他们都是非常聪明的学生。

Input

There are multiple test cases. For each test case, there will be one line of input having two integers N (0 < N <= 10^8) and k (0 < k <= 100). Input terminates when both N and k are zero.
有多个测试用例。对于每个测试案例,将有一行输入具有两个整数N(0 <N <= 10 ^ 8)和K(0 <K <= 100)。当N和k都为零时输入终止。

Output

For each case, print the winner's name in a single line.
对于每种情况,请在一行中打印获胜者的姓名。

Sample Input

1 1
30 3
10 2
0 0

Sample Output

Jiang
Tang
Jiang
解题思路:简单的巴什博弈。题目的意思就是谁先写到数字N或者是超过N谁就输,换句话说,谁只要所选数字到达n-1,谁就赢。规则是先手刚开始只能在[1,k]中编写一个数字,即选择一个不大于k的数字,接下来的规则就是1<=Y-X<=k,我们可以发现,其实Y就是对之前两个人所选数字的累加和,也就是之后轮到的人所选择的数字至少为1,至多为k。到这,所有条件已经满足巴什博弈的模型了。我们将问题转换一下,现有N-1这个和数,要求每次选择减去一个不大于k的数字,谁最后减去一个数字后和数变为k+1,谁就赢,因为接下来的人选择减去的数字不超过k,即最后和数剩下不超过k,再轮到的人都能一次减掉剩下的和数,即此时轮到的人必胜。
结论:当(n-1)%(k+1)==0,后手“Jiang”必赢,否则先手“Tang”必赢。
AC代码:
 #include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
while(cin>>n>>k && (n+k)){
if((n-)%(k+)==)cout<<"Jiang"<<endl;//后手必赢
else cout<<"Tang"<<endl;//先手必赢
}
return ;
}