hdu 1719 博弈水體

Stone Game Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2071    Accepted Submission(s): 576       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題目大意：（取石子游戲）有n個箱子，體積為Si，當前箱子裡的石子數為Ci。兩個人輪流往箱子裡放石子，而且每一次放是數量都有限制，不能超過當前箱子內石子數的平方。例如箱子裡有3顆石子，那麼下一個人就可以放1~9顆石子，直到箱子被裝滿。當有一方放不下石子時游戲結束，最後放不下石子的人輸。  思路：分割成多個小游戲 異或SG函數值

#include<stdio.h>
#include<string.h>
int get_sg(int sz,int ct)
{
    int i;
     for(i=1;i<=1001;i++)
        if(i+i*i>=sz)
        {
           break;
        }
      if(ct==i-1||ct==sz) return 0;
      if(ct>=i) return sz-ct;
      return get_sg(i-1,ct);
}
int main()
{
    int cas,i,j,k=0,n,sum,sz,ct;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n) break;
        sum=0;
        while(n--)
        {
            scanf("%d %d",&sz,&ct);
            if(ct==0||sz==0) continue;
            sum^=get_sg(sz,ct);
        }
        printf("Case %d:\n",++k);
        if(sum!=0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}