2玩家A和B的玩游戏，其中一些的 N 的 玩家A，使第一招：放;双方球员发挥交替进行。 在每个移动玩家需要数n，选择一个数字的我的这样的 2 ^ I＆LT; ñ的和替代的 N 的用的 K = N - 2 ^我的当且仅当1秒中的 K 大于或等于1秒中的二进制重新presentation的 N 的数 在游戏的时候没有球员可以使一招，即不存在结束这样的的我的 2 players A & B are playing a game involving a number n Player A makes the first move & both players play alternately. In each move the player takes the number n,chooses a number i such that 2^i < n and replaces n with k = n - 2^i iff the number of 1s in the binary representation of k is greater than or equal to the number of 1s in the binary representation of n Game ends when no player can make a move, ie there does not exist such an i

例如：

n = 13 = b1101

只能I = 1

k = n - 2^i = 11 = b1011

此外，唯一可能的I = 2

Again,only possible i = 2

k = n - 2^i = 7 = b111

由于玩家A不能做任何更多的动作，玩家B赢

Since Player A cant make any more moves, Player B wins

我推断，在任何步骤，我们只能选择一个我，这样有一个0在n的二进制再presentation相应的位置。照片 例如： 如果n = 1010010，那我也只能是{0,2,3,5}。 但我不能将任何further.A极大极小的算法是不完全打击我，我会AP preciate提前任何help.Thanks

I've deduced that at any step,we can only choose an i,such that there is a 0 at the corresponding position in the binary representation of n. For Example: if n=1010010,then i can only be {0,2,3,5}. But I cant move any further.A minimax algorithm isnt exactly striking me.I would appreciate any help.Thanks in advance

推荐答案

假定n是不是太大了，我们可以用动态规划来解决这个问题。 定义一个数组A [1：n]，其中A [1]再presents是否球员，我会赢得输入我。 让我们用跨pretation：

Assuming n is not too big, we can use dynamic programming to solve this problem. Define an array A[1:n], where A[i] represents whether player i will win on input i. Let's use the interpretation:

   A[i] = 1, if A wins on input i,
   A[i] = 0, if A loses on input i.

现在可以计算自下而上如下：

Now A can be computed bottom-up as follows:

A[1] = 0, A[2] = 1.
For j=3:n { 
      Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
                              (number of 1's in i >=  number of 1's in j)
      Otherwise  Assign A[j] = 0 
}