环形博弈"/>

环形博弈

博弈的题很多，我就用两道经典题来讲解一下。

SDUT 3253

 

 

Game!

Problem Description

One day, zbybr is playing a game with blankcqk, here are the rules of the game:

There is a circle of N stones, zbybr and blankcqk take turns taking the stones.

Each time, one player can choose to take one stone or take two adjacent stones.

You should notice that if there are 4 stones, and zbybr takes the 2nd, the 1st and 3rd stones are still not adjacent.

The winner is the one who takes the last stone.

Now, the game begins and zbybr moves first.

 

If both of them will play with the best strategy, can you tell me who will win the game?

Input

The first line of input contains an integer T, indicating the number of test cases (T≈100000).

For each case, there is a positive integer N (N ≤ 10^18).

Output

Output the name of the winner.

Sample Input

2
1
2

Sample Output

zbybr
zbybr

题目大意：zbybr先手，谁将环形石子最后一个拿走谁赢。这里我们用环形的博弈，先手只能在他能拿石子个数内取胜，否则后手赢。因为当石子个数大于先手能拿的个数，这里我们可以将他们围成一个环形，后手总是拿与先手相对的石子，比如先手拿完后，剩下奇数个，后手拿与先手相对的石子，为偶则拿相对的两个，这样总可以让先手输。

代码如下：

#include <stdio.h>
#include <string.h>
int main()
{int t;scanf("%d",&t);while(t--){long long int n;scanf("%lld",&n);if(n<=2)printf("zbybr\n");elseprintf("blankcqk\n");}return 0;
}

 

 

 

HDU 3951

 

 

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<=109,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

2
3 1
3 2

Sample Output

Case 1: first
Case 2: second

题目大意：T组数据，每组给两个数据，N为硬币个数，K为一次拿硬币的最多个数。按照上题题解，此题类似，总是后手拿环形中先手相对的硬币，保证所剩硬币是对称的，这样就能保证后手赢了。

代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int main()
{int t,n,m,i;scanf("%d",&t);for(i=1; i<=t; i++){scanf("%d%d",&m,&n);printf("Case %d: ",i);if(n==1)if(m%2==1)printf("first\n");elseprintf("second\n");else{if(n>=m)printf("first\n");elseprintf("second\n");}}return 0;
}

 

 

萌新代码，如有不足，多多见谅^_^