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函数题目。

博弈论 SG函数

SG函数和SG定理【详解】

对于这道题目设盒子容量为s，盒子里有c块石头，求得最大值p使得p*p+p<s，p点则为必败点，若c=p则当前状态必败，此点没有后继状态，所以SG值为0，若c>p则当前状态必胜，此点SG值为s-c

为什么返回SG值为s-c

若c<p则当前状态无法确定，用递归SG(p, c)继续寻找确定的状态

sg(p,c)。

如果求得x*x+x < p。

如果c = x。那么接下来的玩家就不能到(S,p)这个点。

所以下下个轮到的玩家可以达到(s,p)这个点。则下下下个玩家就不能到S。而下下下个玩家可以到S。

也就是说 先手必败。

而如果C>X。那么下一个玩家就可以达到(S,p)这个点。先手必胜。

如果C<X,继续递归。

###　——为什么递归传参为p和c

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
}

int cnt;
int n;
int s, c;
int ans;

int SG(int s, int c) {
	int p = sqrt((double)s);
	while (p * p + p >= s) {
		--p;
	}
	if (c > p) {
		return s - c;
	}
	else if (c == p) {
		return 0;
	}
	else {
		return SG(p, c);
	}
}

int main() {
	//fre();
	cnt = 1;
	while (~scanf("%d", &n), n) {
		ans = 0;
		while (n--) {
			scanf("%d%d", &s, &c);
			ans ^= SG(s, c);
		}
		printf("Case %d:\n", cnt++);
		if (ans) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}
    return 0;
}