博弈|hdu1729 Stone Game
Stone Game
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2263 Accepted Submission(s): 645
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值 ,就可以看成取石子了,怎么求sg值呢,我们首先知道,对于n,k,一定存在 一个p使得p+p*p
#include ()
#include
#include
using namespace std;
int getsg(int n,int k){
int p=sqrt(n);
while(p+p*p>=n)
p--;
if(p
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 自助餐博弈论
- 足尖上的博弈
- 牛客练习赛67-C、牛牛爱博弈
- Game|Game on Plane(博弈 SG)
- 《cornerstone》
- 牛牛爱博弈_牛客练习赛67
- 电影《男人花》发布终极预告|电影《男人花》发布终极预告 江湖险斗男人博弈
- 集训队每周一赛 2020-03-26(思维/构造+数学+博弈)
- 转型中的博弈(医学影像人工智能落地基层为何这么难())
- 年末福利!专业级研发项目管理工具CORNERSTONE开源版正式上线!