转载请注明出处:http://blog.csdn.net/cxb569262726/article/details/7841521
题目链接:
http://poj.org/problem?id=3922
http://acm.hdu.edu.cn/showproblem.php?pid=2486
http://acm.hdu.edu.cn/showproblem.php?pid=2580
A simple stone game
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 174Accepted Submission(s): 79
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.
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).
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 Inpu
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
题目大意:给定整数n和k。有n个石头,两个人来取。先手可以取1~n-1个。接下来每次最多能取上一个人取的k倍,即1~k*n; 求先手是否一定能赢!能赢输出第一次最少取几个。否则输出lose。
PS:我想这种变态题目的原因: 今天早上比赛时没人做出来,到了晚上貌似还是没人会,不幸抽签中奖,由我讲解这题。。。。O M G!! 参照网上代码,找了好久的规律!最后时刻想出来了。可惜还是准备不充分,没能表达清楚。。。
思想:找规律 然后 博弈,还有点dp的思想。。。
以下是代码以及解答思路:附上涂鸦一副
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<set>
#include<vector>
#define MAXN 15
#define INF 1000
using namespace std;
int no[2000000],maxok[2000000];//no储存的是lose的数。 maxok【i】存的是在i之前能组成的最大的数;
int main()
{
int i,j,n,m,k,t,c,ca=0;
for(scanf("%d",&t);t--;)
{
ca++;
scanf("%d%d",&n,&k);
if(n<=k+1)//n<=k+1时一定是输;
{
printf("Case %d: lose\n",ca);
continue;
}
int x=0,y=0;
no[0]=maxok[0]=1;
while(no[x]<n)
{
x++;
no[x]=maxok[x-1]+1;//在x之前,最大的能符合的数是maxok【x-1】、加1后就不符合。
while(no[y+1]*k<no[x])//找小于no[x]的最大数:例子k=3时有15得到4
y++;
if(no[y]*k<no[x])//前面得到的数可能不符合条件
maxok[x]=no[x]+maxok[y];//如果符合直接得no[x]+maxok[y];例子中推得15+maxok[3]
else
maxok[x]=no[x];//否则能组成最大的数为本身。
}
if(no[x]==n)//刚好组成n 说明这个数属于no数组。即不能由符合条件的数组成,lose!
{
printf("Case %d: lose\n",ca);
continue;
}
int ans;
while(n)
{
if(n>=no[x])//不断的减去最大的数,剩下的最小的数就是了。
{
ans=no[x];
n-=no[x];
}
x--;
}
printf("Case %d: %d\n",ca,ans);
}
return 0;
}
/*
k=3时:
no={1,2,3,4,6,8,11,15,21,29
maxok=1,2,3,5,7,10,14,20
*/
分享到:
相关推荐
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ 1328 java做!雷达问题!java版本!AC答案~
北大POJ2002-Squares 解题报告+AC代码
poj分类poj分类poj分类poj分类
POJ题解 个人写法 线段树每个人都不一样
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友