取石子游戲

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1304????Accepted Submission(s): 732

Problem Description 1堆石子有n個(gè),兩人輪流取.先取者第1次可以取任意多個(gè)，但不能全部取完.以后每次取的石子數(shù)不能超過上次取子數(shù)的2倍。取完者勝.先取者負(fù)輸出"Second win".先取者勝輸出"First win".

?

Input 輸入有多組.每組第1行是2<=n<2^31. n=0退出.

?

Output 先取者負(fù)輸出"Second win". 先取者勝輸出"First win".
參看Sample Output.

?

Sample Input 2 13 10000 0

?

Sample Output Second win Second win First win

?

Source ECJTU 2008 Autumn Contest

?

Recommend lcy //網(wǎng)上稱這是 斐波切博弈 //2,3,4,5,6都是很容易推知的 //其中對于一個(gè)n，第一次最多不能拿超過n/3，這點(diǎn)很肯定 //那么對于2,3,5,8這些必輸點(diǎn)來講就只要后面適當(dāng)?shù)娜?shù)可以到這些點(diǎn)就可以了，那么就可以讓對方輸 //比如12到8相差4，4個(gè)數(shù)先取的勝，先取的人可以使之是8個(gè)，那么第二個(gè)人就數(shù)了 //二對于13，到8相差5,5個(gè)數(shù)先取的必輸、那么第二個(gè)人可以使之到8，那么第一個(gè)人就輸了 //以此類推下去、、、、、

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int f[50];
int main()
{
??? int i,n;
??? f[0]=2;
??? f[1]=3;
??? for(i=2;i<44;i++)
???? f[i]=f[i-1]+f[i-2];
??? while(scanf("%d",&n),n)
??? {
?????? for(i=0;i<44;i++)
??????? if(n==f[i])
???????? break;
?????? if(i<44)
??????? printf("Second win\n");
?????? else
??????? printf("First win\n");
??? }

??? return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/372465774y/archive/2012/08/01/2618312.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的hdu 2516 取石子游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。