2014
03-23

# Number Game

● Carl picks a number, N, between 1 and 1, 000, 000, 000.
● Carl and Ellie take turns subtracting an integer (between 1 and 20) from N. Carl plays fi rst, and the winner is the one who subtracts off a number to get 0.
For example, suppose Carl picks the number 50. He subtracts off the number 5, leaving 45. Ellie subtracts off 17, leaving 28. Carl subtracts off 8, leaving 20. Finally, Ellie subtracts off 20, leaving 0, and wins!Frankly, Ellie would rather sleep than play this game, so she has reprogrammed the GPS (which isn’t
necessary in this region, anyway) to play for her instead. Her method of choosing a number is straightforward:
● If on a given turn, the number remaining is 20 or less, then she picks that number and wins.
● Otherwise, her choice of number is completely determined by the number Carl just picked, as follows.Before the game starts, Ellie chooses 20 random numbers, 1 <= a1, a2, a3, … , a20 <= 20. Then whenever Carl subtracts off the number k, Ellie responds by subtracting off the number ak (unless she can win).Carl needs your help! To help stay motivated playing this game, he would like to know if there exists a winning strategy for him, given the numbers N and a1, a2, a3, … , a20 .

Each input case begins with the number N on a line by itself; the next line contains the numbers a1, a2, … , a20 ,separated by spaces. Input terminates with a line containing 0.

Each input case begins with the number N on a line by itself; the next line contains the numbers a1, a2, … , a20 ,separated by spaces. Input terminates with a line containing 0.

42
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
0

Carl can't win
HintIn this example, since Carl chooses N to be 42, it turns out that he has no winning strategy. (Indeed,whichever number he initially subtracts off, Ellie will subtract
off a number leaving 21 for Carl. Then whatever number Carl subtracts off next, Ellie will be left with a number between 1 and 20, and she wins!) 

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|Author: WiYR
|Created Time.: 2014-2-16 15:13:56
|File Name: O.cpp
|Description:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
typedef long long ll;
const double eps=1e-7;
const int inf=0x7FFFFFFF;
#define rep(i,n) for(int i=0;i<n;i++)
#define mset(a,i) memset(a,i,sizeof(a))

using namespace std;
int vis[2][1 << 20];
int p[25];
int a[25], ans[25];
int m, n;
int add(int x, int val) {
val |= p[x];
for(int i = 2; i + x <= 20; i ++)if(val & p[i]){
val |= p[i + x];
}
return val;
}
bool dfs(int val, int step) {
if(vis[step][val] != -1)
return vis[step][val];
int tmp;
rep(i, n)if(! (val & p[a[i]])) {
tmp = add(a[i], val);
bool ret = dfs(tmp, step ^ 1);
if(step && !ret) {
vis[1][val] = 0;
vis[0][val] = 1;
return false;
}
if(!step && ret) {
vis[0][val] = 1;
vis[1][val] = 0;
return true;
}
}
vis[1][val] = 1;
vis[0][val] = 0;
return step == 1;
}
int main() {
int T, cas = 0, val;
p[1] = 1;
for(int i = 2; i <= 21; i ++)
p[i] = p[i - 1] << 1;
mset(vis, -1);
vis[1][p[21] - 1] = 1;
vis[0][p[21] - 1] = 0;

scanf("%d", &T);
while(T --) {
scanf("%d", &n);
val = p[21] - 1;
rep(i, n) {
scanf("%d", &a[i]);
val ^= p[a[i]];
}
m = 0;
int tmp;
rep(i, n) {
tmp = add(a[i], val);
if(dfs(tmp, 1))
ans[m ++] = a[i];
//			printf("%d ", vis[0][p[21] - 1]);
}
printf("Scenario #%d:\n", ++ cas);
if(m) {
printf("The winning moves are:");
sort(ans, ans + m);
rep(i, m) {
printf(" %d", ans[i]);
}
puts(".\n");
} else {
puts("There is no winning move.\n");
}
}
return 0;
}

1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)