0%

取石头游戏

题目

两个足够聪明的人玩轮流取石头的游戏,谁取到最后一个石头谁就赢了,他们一次只能取1个、3个、7个或8个石头,写一程序判断n个石头时先取的人是输还是赢。

输入格式:

一个整数n,其值不超过10000000。

输出格式:

如果先取的人赢,请以单独一行输出1,否则输出0。

输入样例:

这里是3组输入。

1
2
3
1
10
300

输出样例:

1
2
3
1
1
0

初始解法(内存超限)

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时,先手必输。

参考

取石头游戏