2013
12-21

# Stone Game

This game is a two-player game and is played as follows:

1. There are n boxes; each box has its size. The box can hold up to s stones if the size is s.
2. At the beginning of the game, there are some stones in these boxes.
3. The players take turns choosing a box and put a number of stones into the box. The number mustn’t be great than the square of the number of stones before the player adds the stones. For example, the player can add 1 to 9 stones if there are 3 stones in the box. Of course, the total number of stones mustn’t be great than the size of the box.
4.Who can’t add stones any more will loss the game.

Give an Initial state of the game. You are supposed to find whether the first player will win the game if both of the players make the best strategy.

The input file contains several test cases.
Each test case begins with an integer N, 0 < N ≤ 50, the number of the boxes.
In the next N line there are two integer si, ci (0 ≤ ci ≤ si ≤ 1,000,000) on each line, as the size of the box is si and there are ci stones in the box.
N = 0 indicates the end of input and should not be processed.

For each test case, output the number of the case on the first line, then output “Yes” (without quotes) on the next line if the first player can win the game, otherwise output “No”.

3
2 0
3 3
6 2
2
6 3
6 3
0

Case 1:
Yes
Case 2:
No

by—cxlove

HDU 1729

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
int get_sg(int s,int c){
int q=sqrt((double)s);
while(q+q*q>=s)
q--;
if(c>q) return s-c;
else return get_sg(q,c);
}
int main(){
int n,cas=0;
while(scanf("%d",&n)!=EOF&&n){
int s,c;
printf("Case %d:\n",++cas);
int ans=0;
while(n--){
scanf("%d%d",&s,&c);
ans^=get_sg(s,c);
}
if(ans)
puts("Yes");
else
puts("No");
}
return 0;
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环