Nim
問題概要
解法
i : プレイヤー番号(0〜2n)
j : 残りの石の数
dp[i][j] := 必勝法が存在するか否か
j = 1 のときは当然その一個を取らなければいけないので必ず負けるので
dp[i][1] = 0
あとは j が少ない順にループを回して
dp[i+1][j-k] (1 <= k <= m[i])
に負ける場合が含まれる場合は
dp[i][j] = 1
それ以外の場合は
dp[i][j] = 0
この調べ方なら自分は次の相手に対する勝ち負けを判定していき,
それが一周回っていくので
0番のプレイヤーの勝敗がそのチームの勝敗になる.
答えはdp[0][s]
コード
(1230.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <cstdio>
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
using namespace std;
int n, S;
int M[21];
int main(){
while(scanf("%d", &n), n){
scanf("%d", &S);
rep(i,2*n) scanf("%d", M+i);
int dp[21][(1<<13)+1] = {-1};
repi(j, 1, S+1)
rep(i, 2*n)
if(j == 1) dp[i][j] = 0;
else{
repi(k, 1, M[i]+1)
if(j - k < 1) break;
else if(dp[(i+1)%(2*n)][j-k] == 0)
dp[i][j] = 1;
if(dp[i][j] == -1) dp[i][j] = 0;
}
printf("%d\n", dp[0][S]);
}
return 0;
}
|