首页 > 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


  1. 为了方便你理解,那我明确的告诉你:如果删评论应该从这段删:【我不認識’雷子’, 但見’风语者’你不斷挑引他的留言. 有仇還是我看錯嗎?’雷子’的思維不錯, 有值得一看的價值.’风语者’你的留言, 只能被看見你的動機, 但不存在內容.有仇的話, 說出來大家

  2. 好的没有关系,另外我想问一下,如果我启用了大尺寸的缩略图 比如 620 200 但是文章中有一些宽度只有600的图就无法正常截取 200的高度,这个是什么原因呢?

  3. ꞃ美乳ꞃ泰州写真多多妹妹潮装曝光美女图片库史上最小比基尼比赛黑丝美女诱惑av在线视频观看网站唯美女生图片mm88.gq

  4. 艳门照Ҁ回家的诱惑全集60最新av刘伊心 比基尼比基尼小姐泡温泉美女故事你究竟有几个好妹妹歌词美女人体写真www.mm88.ml

  5. a货专卖店ີPRADA(普拉达)ANLATINA(娃伦迪儿)NINE WEST(玖熙)DuneChrome Hearts(克罗心)阎双/哈品S.T.Dupont(都彭)shechipin.ga