首页 > 代码库 > HDUOJ--------A simple stone game(尼姆博弈扩展)(2008北京现场赛A题)
HDUOJ--------A simple stone game(尼姆博弈扩展)(2008北京现场赛A题)
A simple stone game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 312 Accepted Submission(s): 167
Problem Description
After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier.
The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k × m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.
The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k × m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.
Input
The first line contains a integer t, indicating that there are t test cases following.(t<=20).
Each test case is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).
Each test case is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).
Output
For each test case, output one line starting with “Case N: ”, N is the case number. And then, if the first player can ensure a winning, print the minimum number of stones he should take in his first turn. Otherwise, print "lose". Please note that there is a blank following the colon.
Sample Input
5
16 1
11 1
32 2
34 2
19 3
Sample Output
Case 1: lose
Case 2: 1
Case 3: 3
Case 4: lose
Case 5: 4
Source
2008 Asia Regional Beijing
题意:
一堆石子两个人轮流抢,每次至少要取走一个。先取的人第一次可以取任意多个,但是不能全部取完,之后每个人取石子时,能取的数目最多不能超过对手刚取石子数的k倍(k为给定常量)。取走最后一个石子的人算赢。
在两人都以最优策略进行游戏时,先手要么必胜要么必负,必胜还是必负取决宇一开始有多少石子,本题就是告诉你开始的石子数目,你需要判断先手必胜还是必负,然后对先收必胜的情况,要算出先手一方第一次至少需要取多少个石子。
代码:
1 #include<stdio.h> 2 #define maxn 1000000 3 int n , k ; 4 5 int a[maxn+1]; 6 int r[maxn+1]; 7 void solve() 8 { 9 int i,j; 10 a[0]=a[0]=0; 11 for(i=1,j=0 ;i<=maxn;i++) 12 { 13 a[i]=r[i-1]+1; 14 while(j+1<i && a[j+1]*k<a[i]) 15 j++; 16 r[i]=a[i]+r[j]; 17 if(r[i]>=n) break; 18 } 19 if(i>maxn) 20 { 21 printf("un solvable\n"); 22 return ; 23 } 24 if(a[i]==n) 25 { 26 printf("lose\n"); 27 return ; 28 } 29 for( ; i>=1 ;i--) 30 { 31 if(n==a[i]) 32 { 33 printf("%d\n",n); 34 return ; 35 } 36 else if(n>a[i]) n-=a[i]; 37 } 38 printf("logic error\n"); 39 } 40 int main() 41 { 42 int ca ,cc=0; 43 scanf("%d",&ca); 44 while(ca-->0) 45 { 46 scanf("%d %d",&n,&k); 47 printf("Case %d: ",++ cc); 48 solve(); 49 } 50 return 0; 51 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。