• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			POJ 2068 Nim
		
            
		
              1/*
              2POJ 2068 Nim
              3
              4
              5----問題描述：
              6
              7Let'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
              9In 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
             11Let'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
             13In 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
             15You 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
             17Incidentally, 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
             19
             20----輸入：
             21
             22The 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
             24n S M1 M2 . . . M2n 
             25
             26where 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
             28
             29----輸出：
             30
             31The output should consist of lines each containing either a one, meaning your team has a winning strategy, or a zero otherwise.
             32
             33
             34----樣例輸入：
             35
             361 101 4 4
             371 100 4 4
             383 97 8 7 6 5 4 3
             390
             40
             41
             42----樣例輸出：
             43
             440
             451
             461
             47
             48
             49----分析：
             50
             51博弈DP ，記憶化搜索。
             52
             53
             54*/
             55
             56
             57#include <iostream>
             58#include <cstdio>
             59#include <cstring>
             60
             61using namespace std;
             62
             63const int N = 29;
             64
             65int n, s, m[ N ], f[ N ][ (1<<13) + 9 ];
             66
             67        // 到第 i 個人，面對 j 個石子，奇數(shù)方勝則為 1，敗則為 0 .
             68int dp( int i, int j ) {
             69        if ( -1 != f[ i ][ j ] ) {
             70                return f[ i ][ j ];
             71        }
             72
             73        if ( 0 == j ) {
             74                return ( f[ i ][ j ] = (i & 1) );
             75        }
             76
             77        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
             88int 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 閱讀(885) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久亚洲日韩精品一区二区三区|
久久久久国产一区二区|
久久久噜噜噜久久中文字幕色伊伊|
精品亚洲综合久久中文字幕|
久久国产亚洲精品麻豆|
久久精品成人欧美大片|
国产亚洲精品久久久久秋霞|
精品久久久久久|
久久www免费人成精品香蕉|
亚洲香蕉网久久综合影视|
97精品国产91久久久久久|
久久精品夜色噜噜亚洲A∨|
麻豆亚洲AV永久无码精品久久|
久久精品国产免费|
久久精品人妻中文系列|
亚洲综合久久综合激情久久|
久久精品一区二区三区AV|
久久国产精品免费|
国产精品久久网|
久久亚洲精品无码VA大香大香|
91久久婷婷国产综合精品青草|
一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区|
中文无码久久精品|
久久夜色精品国产噜噜亚洲a|
国产综合成人久久大片91|
国产午夜久久影院|
久久人人爽人人爽人人AV|
亚洲国产香蕉人人爽成AV片久久|
精品综合久久久久久97超人
|
久久精品国产99国产精品澳门|
亚洲欧洲中文日韩久久AV乱码|
久久精品国产久精国产|
久久精品国产亚洲AV电影|
久久亚洲精品无码AV红樱桃|
久久艹国产|
久久人人爽人爽人人爽av|
国产福利电影一区二区三区，免费久久久久久久精
|
蜜臀av性久久久久蜜臀aⅴ麻豆
|
无码任你躁久久久久久老妇|
国产福利电影一区二区三区久久老子无码午夜伦不
|
久久精品国产一区二区三区日韩|