coreBugZJ

此 blog 已棄。

POJ 2068 Nim

/*
2

POJ 2068 Nim
3

----問題描述：
6

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.
8

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.
10

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.
12

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.
14

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.
16

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!
18

----輸入：
21

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.
23

n S M1 M2 . . . M2n
25

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.
27

----輸出：
30

The output should consist of lines each containing either a one, meaning your team has a winning strategy, or a zero otherwise.
32

----樣例輸入：
35

1 101 4 4
37

1 100 4 4
38

3 97 8 7 6 5 4 3
39

0
40

----樣例輸出：
43

0
45

1
46

1
47

----分析：
50

博弈DP ，記憶化搜索。
52

*/
55

#include <iostream>
58

#include <cstdio>
59

#include <cstring>
60

using namespace std;
62

const int N = 29;
64

int n, s, m[ N ], f[ N ][ (1<<13) + 9 ];
66

// 到第 i 個人，面對 j 個石子，奇數方勝則為 1，敗則為 0 .
68

int dp( int i, int j ) {
69

if ( -1 != f[ i ][ j ] ) {
70

return f[ i ][ j ];
71

}
72

if ( 0 == j ) {
74

return ( f[ i ][ j ] = (i & 1) );
75

}
76

int k;
78

f[ i ][ j ] = 1 - (i & 1);
79

for ( k = 1; (k <= j)&&(k <= m[ i ]); ++k ) {
80

if ( (i & 1) == dp( i%n+1, j - k ) ) {
81

f[ i ][ j ] = (i & 1);
82

break;
83

}
84

}
85

return f[ i ][ j ];
86

}
87

int main() {
89

int i;
90

while ( (1 == scanf( "%d", &n )) && (0 < n) ) {
91

scanf( "%d", &s );
92

n <<= 1;
93

for ( i = 1; i <= n; ++i ) {
94

scanf( "%d", m+i );
95

}
96

memset( f, 0xFF, sizeof(f) );
97

printf( "%d\n", dp( 1, s ) );
98

}
99

return 0;
100

}
101

posted on 2012-06-04 16:03 coreBugZJ 閱讀(907) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內作業

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 2068 Nim