首页 > ACM题库 > HDU-杭电 > HDU 4764-Stone-博弈论-[解题报告]HOJ
2015
09-17

HDU 4764-Stone-博弈论-[解题报告]HOJ

Stone

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

1 1
30 3
10 2
0 0

样例输出:

Jiang
Tang
Jiang

线性博弈的题目,碰上博弈的题目一定不要怕,无论如何都要尝试推一下。

这个题嘻嘻分析其实很简单,最大取到n-1,那么,第一次取到n-1的人肯定是获胜方,那么再从n-1向前推,第一次取到n-k-1到n-2之间数字的人,下一个人一定会取到n-1,所以n-k-1到n-2之间肯定是失败方,再向前推,第一次取到n-k-2的人肯定是获胜方,因为下一个人肯定只能取到n-k-1到n-2之间的数字,一次类推,这是一个循环,循环节便是k+1,如果长度刚好等于循环节的整数倍,那么先手必败,否则先手胜。

附代码:

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int main()
{
    int n,k;
    while (cin>>n>>k&&n+k)
    {
        n=n-1;
        k=k+1;
        n=n%k;
        if (n!=0)
            cout<<"Tang"<<endl;
        else
            cout<<"Jiang"<<endl;
    }
}

参考:http://blog.csdn.net/u011663071/article/details/39060277