游戏难题，两名玩家玩更换硬币价值的游戏
Game puzzle, two players playing the game of replacing coin values
我们已经给出了 n 个硬币，每个硬币的面值都为 k。
现在有nick和james两个玩家轮流玩游戏。在每一轮中，玩家可以选择任何硬币并将其替换为多个面值总和等于替换硬币的硬币。每个新硬币必须具有相同的面值。还给出了整数p，它是一个限制，表示玩家不能使用面值小于p的硬币进行置换。
所有玩家都给出了无限数量的无限面值的硬币。
因此样本输入将为 n,k,p，其中 n 为否。每个面值的硬币的数量是 k 并且限制 p 如上所述。如果两人都打得最好，尼克先开始，谁将赢得比赛。如果玩家不能玩轮到他就输了游戏（意味着不能更换任何硬币）。
是nim问题还是DP游戏？我们如何解决这个问题？
这绝对是Nim is the right way to think about: it is a two-player game, it is perfect information meaning both players know the full game state at all times, there is no element of chance, it is an impartial game meaning the same moves are available to both players, and you lose if you are unable to move. So the Sprague–Grundy theorem applies to this game; every position in the game is equivalent to a nimber那种游戏。我们可以解决一个位置，通过计算位置的数量来找出谁将在给定的最佳游戏中获胜；当且仅当数字不为零时，位置才是先手获胜。
然而，对于这个特定问题来说，这完全没有必要，因为起始位置的所有硬币都具有相同的价值。
如果硬币数量为偶数，则玩家2采用镜像策略获胜。将硬币成对匹配，然后无论对手在一枚硬币上下什么棋，都会在另一枚硬币上做出镜像。成对匹配生成的硬币并继续在它们上进行镜像。
如果有奇数个硬币，则玩家 1 获胜，将其中一个硬币分成最小可能值 >= p 的硬币，这样就不能对这些硬币进行更多移动.然后玩家1对剩余的偶数个硬币采用上面给出的镜像策略。
有一种特殊情况：如果硬币的面值已经使玩家1无法下手，那么无论硬币的数量是奇数还是偶数，玩家2总是赢家.
所以答案是：玩家 1 获胜当且仅当 n 是奇数且 k 的因子 >= p。显然不会有更有效的解决方案。
我们已经给出了 n 个硬币，每个硬币的面值都为 k。
现在有nick和james两个玩家轮流玩游戏。在每一轮中，玩家可以选择任何硬币并将其替换为多个面值总和等于替换硬币的硬币。每个新硬币必须具有相同的面值。还给出了整数p，它是一个限制，表示玩家不能使用面值小于p的硬币进行置换。 所有玩家都给出了无限数量的无限面值的硬币。
因此样本输入将为 n,k,p，其中 n 为否。每个面值的硬币的数量是 k 并且限制 p 如上所述。如果两人都打得最好，尼克先开始，谁将赢得比赛。如果玩家不能玩轮到他就输了游戏（意味着不能更换任何硬币）。
是nim问题还是DP游戏？我们如何解决这个问题？
这绝对是Nim is the right way to think about: it is a two-player game, it is perfect information meaning both players know the full game state at all times, there is no element of chance, it is an impartial game meaning the same moves are available to both players, and you lose if you are unable to move. So the Sprague–Grundy theorem applies to this game; every position in the game is equivalent to a nimber那种游戏。我们可以解决一个位置，通过计算位置的数量来找出谁将在给定的最佳游戏中获胜；当且仅当数字不为零时，位置才是先手获胜。
然而，对于这个特定问题来说，这完全没有必要，因为起始位置的所有硬币都具有相同的价值。
如果硬币数量为偶数，则玩家2采用镜像策略获胜。将硬币成对匹配，然后无论对手在一枚硬币上下什么棋，都会在另一枚硬币上做出镜像。成对匹配生成的硬币并继续在它们上进行镜像。
如果有奇数个硬币，则玩家 1 获胜，将其中一个硬币分成最小可能值 >= p 的硬币，这样就不能对这些硬币进行更多移动.然后玩家1对剩余的偶数个硬币采用上面给出的镜像策略。
有一种特殊情况：如果硬币的面值已经使玩家1无法下手，那么无论硬币的数量是奇数还是偶数，玩家2总是赢家.
所以答案是：玩家 1 获胜当且仅当 n 是奇数且 k 的因子 >= p。显然不会有更有效的解决方案。