Nim
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 795 | Accepted: 453 |
Description
Let's play a traditional game Nim. You and I are seated across a table and we have a hundred stones on the table (we know the number of stones exactly). We play in turn and at each turn, you or I can remove on to four stones from the heap. You play first and the one who removed the last stone loses.
In this game, you have a winning strategy. To see this, you first remove four stones and leave 96 stones. No matter how I play, I will end up with leaving 92 - 95 stones. Then you will in turn leave 91 stones for me (verify this is always possible). This way, you can always leave 5k+1 stones for me and finally I get the last stone, sigh. If we initially had 101 stones, on the other hand, I have a winning strategy and you are doomed to lose.
Let's generalize the game a little bit. First, let's make it a team game. Each team has n players and the 2n players are seated around the table, with each player having opponents at both sides. Turn around the table so the two teams play alternately. Second, let's vary the maximum number of stones each player can take. That is, each player has his/her own maximum number of stones he/she can take at each turn (The minimum is always one). So the game is asymmetric and may even be unfair.
In general, when played between two teams of experts, the outcome of a game is completely determined by the initial number of stones and the maximum number of stones each player can take at each turn. In other words, either team has a winning strategy.
You are the head-coach of a team. In each game, the umpire shows both teams the initial number of stones and the maximum number of stones each player can take at each turn. Your team plays first. Your job is, given those numbers, to instantaneously judge whether your team has a winning strategy.
Incidentally, there is a rumor that Captain Future and her officers of Hakodate-maru love this game, and they are killing their time playing it during their missions. You wonder where the stones are? Well, they do not have stones but do have plenty of balls in the fuel containers!
In this game, you have a winning strategy. To see this, you first remove four stones and leave 96 stones. No matter how I play, I will end up with leaving 92 - 95 stones. Then you will in turn leave 91 stones for me (verify this is always possible). This way, you can always leave 5k+1 stones for me and finally I get the last stone, sigh. If we initially had 101 stones, on the other hand, I have a winning strategy and you are doomed to lose.
Let's generalize the game a little bit. First, let's make it a team game. Each team has n players and the 2n players are seated around the table, with each player having opponents at both sides. Turn around the table so the two teams play alternately. Second, let's vary the maximum number of stones each player can take. That is, each player has his/her own maximum number of stones he/she can take at each turn (The minimum is always one). So the game is asymmetric and may even be unfair.
In general, when played between two teams of experts, the outcome of a game is completely determined by the initial number of stones and the maximum number of stones each player can take at each turn. In other words, either team has a winning strategy.
You are the head-coach of a team. In each game, the umpire shows both teams the initial number of stones and the maximum number of stones each player can take at each turn. Your team plays first. Your job is, given those numbers, to instantaneously judge whether your team has a winning strategy.
Incidentally, there is a rumor that Captain Future and her officers of Hakodate-maru love this game, and they are killing their time playing it during their missions. You wonder where the stones are? Well, they do not have stones but do have plenty of balls in the fuel containers!
Input
The input is a sequence of lines, followed by the last line containing a zero. Each line except the last is a sequence of integers and has the following format.
n S M1 M2 . . . M2n
where n is the number of players in a team, S the initial number of stones, and Mi the maximum number of stones ith player can take. 1st, 3rd, 5th, ... players are your team's players and 2nd, 4th, 6th, ... the opponents. Numbers are separated by a single space character. You may assume 1 <= n <= 10, 1 <= Mi <= 16, and 1 <= S < 2^13.
n S M1 M2 . . . M2n
where n is the number of players in a team, S the initial number of stones, and Mi the maximum number of stones ith player can take. 1st, 3rd, 5th, ... players are your team's players and 2nd, 4th, 6th, ... the opponents. Numbers are separated by a single space character. You may assume 1 <= n <= 10, 1 <= Mi <= 16, and 1 <= S < 2^13.
Output
The output should consist of lines each containing either a one, meaning your team has a winning strategy, or a zero otherwise.
Sample Input
1 101 4 4 1 100 4 4 3 97 8 7 6 5 4 3 0
Sample Output
0 1 1
/* 题目大意:有两队，每队n个人，两队坐在一个圆形的桌上，奇数序号(1、3、5、…)为第一队，偶数序号为第二队。桌上有S个石头。从1号开始沿着桌子取石头。每个人至少取一个，最多取Mi个，其中最后取石头的人所在的队输。先给你n，S和take数组（1 <= n <= 10, 1 <= Mi <= 16, and 1 <= S < 2^13.），若第一队能赢，输出1，否则输出0. */ /*此题是经典的双人有限制单堆博弈的扩展*/ /* 由于增加了诸多变数，所以本题没有原型那么简洁的数学公式，但是考虑到范围较小，可以用记忆化搜索完成，也可以直接正向DP。 考虑状态(curr,lefts)表示轮到第curr个人游戏时堆里的石子数为lefts，则有: ① Lefts = 0为必胜态； ② Lefts = 1为必败态。 ③ 当lefts > 1时，则搜索所有的 ((curr+1)%n,lefts-k)，其中1<=k<=min(M[curr],lefts),若其中存在必败态，则当前状态为必胜态，否则为必败态。 */ #include<iostream> using namespace std; #define min(a,b) (((a)<(b))?(a):(b)) int dp[30][10000]; //0表示败 int n,s,m[30]; int win( int curr, int lefts ) { if(dp[curr][lefts] != -1) return dp[curr][lefts]; if(lefts == 0) return dp[curr][lefts] = 1; if(lefts == 1) return dp[curr][lefts] = 0; int mn = min(m[curr],lefts); for(int k = 1;k <= mn;k++) { if(win( (curr+1)%n, lefts-k ) == 0) return dp[curr][lefts] = 1; } return dp[curr][lefts] = 0; } int main() { while( cin >> n, n ) { cin >> s; n *= 2; memset(dp, -1, sizeof(dp)); for(int i = 0;i < n;i++) scanf("%d", &m[i]); if( win(0, s) ) printf("1\n"); else printf("0\n"); } return 0; }