总而言之,游戏中有n个塔高m,每转一圈,玩家可以将一个塔减少到一个除以其高度但不等于其高度的数字,目标是让对手在轮到他时没有可能的移动。
例如,如果N=2,M=2
那么第一个玩家输了,因为他唯一能做的动作是将一个塔降低到1号高度,之后另一个玩家唯一能做的动作是将另一个塔降低到1号高度,而现在第一个玩家没有动作要做。
我开始写这篇文章,但它变得太复杂了,我无法真正看到非素数上的“模式”,比如M
。有没有更好的方法让我思考这个问题?
1 --> Lose
1 1 --> Lose
1 1 1 --> Lose
etc.
2 --> Win
2 2 --> Lose
2 2 2 --> Win
2 2 2 2 --> Lose
etc.
3 --> Win
3 3 --> Lose
3 3 3 --> Win
3 3 3 3 --> Lose
etc.
4 --> Win
4 4 --> Lose (see tree below)
4,4 1's turn
/ \
/ \
/ \
/ \
/ \
2,4 1,4 2's turn
/ \ \ / \
/ \ \ / \
/ \ \ / \
1,4 2,2 1,2 1,1 1,2 1's turn
/ \ \ \ \
/ \ \ \ \
1,1 1,2 1,2 1,1 1,1 2's turn
/ \
/ \
1,1 1,1 1's turn
我计算一号或二号选手获胜的方法是
static int Winner(int n, int m)
{
if(m == 1)
return 2;
else if(IsPrime(m))
return n % 2 == 0 ? 2 : 1;
else
{
// ... ??
}
}
编辑:哇,我只是胡乱猜了一下
static int Winner(int n, int m)
{
if(m == 1)
return 2;
else
return n % 2 == 0 ? 2 : 1;
}
它通过了挑战问题的所有测试用例。所以我“解决”了它,却不明白为什么。
最佳答案
我们可以排除从高度1开始的塔我们也可以排除从素数开始的高度如果它们都是质数,那么每个玩家只有一个可能的移动。一次一个塔降到1高,直到都是1,所以谁赢取决于n
是否奇怪。
因此以m
不是1且不是素数的情况为例。
最快的游戏是将所有高度降低到1,这将采取n
移动如果移动结束时剩余的移动次数是偶数,则移动的玩家获胜如果n
是奇数,则第一个玩家获胜。
所以球员们都想在轮到他们的时候再做剩下的动作。玩家可以通过将塔降低到一个基本高度来增加1点剩余的移动。另一个玩家不能在同一个塔上重复这个动作,因为那个塔上只剩下一次移动。这样做的次数是n
所以玩家是否能够在回合中向左移动的次数是偶数取决于n
是否是奇数。