杭電1279 Stone Game（經典博弈）

Stone Game

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2539 Accepted Submission(s): 741


Problem Description 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.

Input 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.

Output 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”.
Sample Input

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

Sample Output

Case 1:
Yes
Case 2:
No
/*
以為很難，結果看了下人家的博客還是SG函數
Time:2014-8-27 21-18
*/
#include 
#include
#include
#include
using namespace std;
int Get_sg(int sum,int x){
	int D=sqrt(sum)+1;
	while(D*D+D>=sum) D--;//找到必敗的臨界點 
	
	if(x>D)//D*D+D=sum  D-1為必勝態，如果大於等於D，則必敗，並且最小值是sum-D 
	return sum-x;//返回能取得最小值即為sg值,
	//是減去 x不是D,即最少取的個數，寫錯了wa了好多次 
	else
	return Get_sg(D,x);//從臨界值開始再向下尋找，找到返回 
} 
int main(){
	int N;
	int d=0;
	while(scanf("%d",&N),N){
		int ans=0;
		int c,sum;
		for(int i=0;i