Coin Game

Problem Description

After hh has learned how to play Nim game, he begins to try another coin game which seems much easier.

The game goes like this:
Two players start the game with a circle of n coins.
They take coins from the circle in turn and every time they could take 1~K continuous coins.
(imagining that ten coins numbered from 1 to 10 and K equal to 3, since 1 and 10 are continuous, you could take away the continuous 10 , 1 , 2 , but if 2 was taken away, you couldn't take 1, 3, 4, because 1 and 3 aren't continuous)
The player who takes the last coin wins the game.
Suppose that those two players always take the best moves and never make mistakes.
Your job is to find out who will definitely win the game.

Input

The first line is a number T(1<=T<=100), represents the number of case. The next T blocks follow each indicates a case.
Each case contains two integers N(3<=N<=10⁹,1<=K<=10).

Output

For each case, output the number of case and the winner "first" or "second".(as shown in the sample output)

Sample Input

3 1

3 2

Sample Output

Case 1: first Case 2: second

题目意思：对于t组样例，有n硬币，编好号，组成环，每一次可以连续的取k个，谁最后取完谁赢。

解题思路：这是一道博弈问题，游戏刚开始的时候所有石子为一条环，先手不可能一次全部取完的情况下，石子就会变成一条链，然而后手只需要创建一个对称的局势就可以取得胜利，就是把这条链分成两条相等的链。我们发现当k=1时，对称局势对游戏没有任何影响，胜负取决于奇偶性；而k>=2时，后手利用对称局势可以取得胜利，先手必输。

#include<stdio.h>

int main()

{

    int t,i,k,n,flag;

    scanf("%d",&t);

    i=;

    while(t--)

    {

        scanf("%d%d",&n,&k);

        if(k>=n)//先手胜利

        {

            flag=;

        }

        else if(k==)

        {

            if(n%==)///奇数先手必胜

                flag=;

            else

                flag=;///偶数后手对称拆，必胜

        }

        else

            flag=;///k>1时后手利用对称局势，必胜

        if(flag==)

            printf("Case %d: first\n",i);

        else

            printf("Case %d: second\n",i);

        i++;

    }

    return ;

}

巴特西

Coin Game

最新文章

热门文章