Cheat in the Game Problem[周末摩思]

Cheat in the Game Problem
Problem Description

Alice and Bob are playing a game. At the beginning, the judge takes out a stone pile of W stones and a black box containing N cards. Every card has a number Ai on it. Alice and Bob takes turns to draw a card from the box. Of course, they will not know the number until they draw the card out of the box. The player then takes away Ai stones from the pile if it is possible. If there are not enough stones, the player draws a card again. The winner is the player who takes away the last stone. Once the box gets empty, they brings back all cards and stones and play the game again until there is a winner.

Now your best friend Alice begs you, the judge, to help her cheat in the game. You have already known the number of cards in the box and their numbers. Given a integer M, You want to know how many values, less or equal to M, W can take so that you can make sure Alice will be the winner of the game.

Input

There are several test cases.
The first line of each test case contains two integers N (1 ≤ N ≤ 10000) and M (1 ≤ M ≤ 100000).
The second line contains N integers Ai (1 ≤ AiM). The input ends with two zeros

Output

For each test case output how many values you can choose for W so that Alice will be the winner without fail.

Sample Input

3 8
1 5 7 
0 0

Sample Output

3

Hint

We say that Alice is surely to win if and only if the possibility that Alice wins is greater than zero and the possibility that Bob wins is zero. For the sample, W = 1, 5, 7.

金手指:有俩人玩一个取石子的游戏,你是裁判。游戏中有W块石头和N张卡片,卡片上分别写着数字Ai。玩家随机抽走一张卡片,按卡片上的数字从石头堆中取走相应数量的石头,如果石头不够,玩家重新抽卡片,取走最后一块石头的玩家获胜;如果石头堆为空仍然未分出胜负,则拿回所有石头和卡片重新开始。

现在先手玩家贿赂了你,请你帮他构造必胜条件。游戏中的卡片是固定的,但W可供你操作。问有多少小于或等于M的W满足要求。

推理与动态规划算法

如果W只能表示成特定的n张卡片上的数字之和,那么:

  • 当n为偶数时,{先手一张,后手一张}循环n/2次拿完石头,后手玩家必胜。
  • 当n为奇数时,{先手一张,后手一张}循环n/2 + 1次拿完石头,先手玩家必胜。

如果W既可以表示成奇数张卡片数字之和,也可以表示成偶数张卡片数字之和,则两人都可能获胜;或者说没有必胜决策。

如果W既无法表示成奇数张卡片数字之和,也无法表示成偶数张卡片数字之和,则W无法用卡片取完,两人会一直玩到天荒地老,你这个裁判就变成了灯泡,而且是长明灯。

所以对题目有用的只有第一个如果分支。

动态规划地搜索整个M范围,定义

  1. bool dp[100000 + 16][2]; // dp[W][0]=true表示W可以分解成偶数个数;dp[W][1]=true表示W可以分解成奇数个数

  1. if (dp[ A[i]][0])
  2.     dp[j][1] = true;    // 偶数+1=奇数
  3. if (dp[ A[i]][1])
  4.     dp[j][0] = true;    // 奇数+1=偶数

满足

  1. if (dp[i][1] && !dp[i][0])  // 只能表示成奇数

的就是符合要求的一个W。

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. int A[10000 + 16];
  8. bool dp[100000 + 16][2]; // dp[W][0]=true表示W可以分解成偶数个数;dp[W][1]=true表示W可以分解成奇数个数
  9.  
  10. int main()
  11. {
  12. #ifndef ONLINE_JUDGE
  13.     freopen(“in.txt”, “r”, stdin);
  14. #endif
  15.     int N, M;
  16.     while (scanf(“%d%d”, &N, &M), N)
  17.     {
  18.         for (int i = 0; i < N; ++i)
  19.         {
  20.             scanf(“%d”, A + i);
  21.         }
  22.         sort(A, A + N);
  23.         memset(dp, 0, sizeof(dp));
  24.         dp[A[0]][1] = true;     // W=A_0可以由A_0这一个数构成
  25.         for (int i = 1; i < N; ++i)
  26.         {
  27.             for (int j = M; j > A[i]; j)
  28.             {
  29.                 if (dp[ A[i]][0])
  30.                     dp[j][1] = true;    // 偶数+1=奇数
  31.                 if (dp[ A[i]][1])
  32.                     dp[j][0] = true;    // 奇数+1=偶数
  33.             }
  34.             dp[A[i]][1] = true;         // W=A_i可以由A_i这一个数构成
  35.         }
  36.         int ans = 0;
  37.         for (int i = 1; i < M + 1; ++i)
  38.         {
  39.             if (dp[i][1] && !dp[i][0])  // 只能表示成奇数
  40.                 ++ans;
  41.         }
  42.         printf(“%d\n”, ans);
  43.     }
  44. #ifndef ONLINE_JUDGE
  45.     fclose(stdin);
  46. #endif
  47.     return 0;
  48. }

Be the first to comment

Leave a Reply

Your email address will not be published.


*