题目
两个足够聪明的人玩轮流取石头的游戏，谁取到最后一个石头谁就赢了，他们一次只能取1个、3个、7个或8个石头，写一程序判断n个石头时先取的人是输还是赢。
输入格式:
一个整数n，其值不超过10000000。
输出格式:
如果先取的人赢，请以单独一行输出1，否则输出0。
输入样例:
这里是3组输入。
输出样例:
初始解法（内存超限）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <algorithm>
using namespace std;
const int maxN = 10000000+1;
int V[4] = {1, 3, 7, 8};
int dp[maxN];
void solve(int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; i >= V[j] && j < 4; j++)
{
int v = V[j];
if (i == v)
{
dp[i] = 1;
break;
}
if (dp[i - v] == 0)
{
dp[i] = 1;
}
}
}
cout << dp[n] << endl;
}
int main()
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
|
最终解法
打印dp数组，发现(n%15)==0,2,4,6时为0，其他都为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
using namespace std;
void solve(int n)
{
int left = n % 15;
if (left == 0 || left == 2 || left == 4 || left == 6)
cout << 0 << endl;
else
cout << 1 << endl;
}
int main()
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
|
证明
n=1~15的结果可直接求得：n=2, 4, 6, 15时，先手必输。
然后只需要保证：n+15胜负仍相同
即：当n>15时，无论先手方如何选取，后手方都存在策略使得总石子数减少15后，取石头的人仍是先手
即：无论先手方如何选取，后手方都有办法拿到这15个石头中的最后一个
而n=15时，先手必输，即后手必胜，也就是说满足上述假设。
所以n+15之后，先手仍然必输。
引申
如果被迫拿到最后一个石子的输，则n%15 =1, 3, 5, 7时，先手必输。
参考
取石头游戏
