• <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>

            Timus 1087(recursion game)

            1087. The Time to Take Stones

            Time Limit: 1.0 second
            Memory Limit: 16 MB
            You probably know the game where two players in turns take 1 to 3 stones from a pile. Looses the one who takes the last stone. We'll generalize this well known game. Assume that both of the players can take not 1, 2 or 3 stones, but k1, k2, …, km ones. Again we'll be interested in one question: who wins in the perfect game. It is guaranteed that it is possible to make next move irrespective to already made moves.

            Input

            The first line contains two integers: n and m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50) — they are an initial amount of stones in the pile and an amount of numbers k1, …, km. The second line consists of the numbers k1, …, km, separated with a space (1 ≤ kin).

            Output

            Output 1, if the first player (the first to take stones) wins in a perfect game. Otherwise, output 2.

            Sample

            input output
            17 3
                        1 3 4
                        
            2
                        
            Problem Author: Anton Botov
            Problem Source: The 3rd high school children programming contest, USU, Yekaterinburg, Russia, March 4, 2001



            /*
            "Looses the one who takes the last stone" —— the one takes the last 
            stone loses the game ! 
            */ 
            #include 
            <stdio.h>
            #include 
            <memory>
            #include 
            <iostream>
            #include 
            <algorithm>
            #include 
            <cstring>
            #include 
            <vector>
            #include 
            <map>
            #include 
            <cmath>
            #include 
            <set>
            #include 
            <queue>
            #include 
            <time.h> 
            #include 
            <limits>
            using namespace std; 
            #define N 10005
            #define M 55
            int step[M], n, m; 
            bool state[N]; 
            bool input(){
                
            if(scanf("%d%d"&n, &m) == EOF) return false
                
            int i; 
                
            for(i = 0; i < m; i++) scanf("%d", step+i);
                
            return true
            }
            void solve(){
                memset(state, 
            0sizeof(bool* (n+1)); 
                
            int i, j, u; 
                
            for(i = 1; i <= n; i++){
                    
            for(j = 0; j < m; j++){
                        
            if((u = i - step[j]) >= 0){
                            
            if(u == 0){
                                state[i] 
            = false
                            }
            else{
                                
            if(!state[u]){
                                    state[i] 
            = true
                                    
            break
                                }
                            }
                        }
                    }
                }
                
            //for(i = 0; i <= n; i++) printf("s[%d]=%d\n", i, state[i]);
                if(state[n]) printf("1\n");
                
            else printf("2\n");
            }
            int main(){
            #ifndef ONLINE_JUDGE
                freopen(
            "in.txt""r", stdin); 
                
            //freopen("out.txt", "w", stdout); 
            #endif 
                
            while(input()) solve(); 
                
            return 0;
            }

            posted on 2011-01-18 15:23 tw 閱讀(139) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): Timus題解

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿

            文章分類(lèi)

            文章檔案

            搜索

            最新評(píng)論

            一本综合久久国产二区| 91视频国产91久久久| 久久久久香蕉视频| 色婷婷噜噜久久国产精品12p| 三级片免费观看久久| 久久综合九色综合网站| 美女写真久久影院| 伊人久久大香线蕉综合5g| 99久久国产宗和精品1上映| 国内精品久久久久伊人av| 欧美久久一级内射wwwwww.| 国内精品人妻无码久久久影院 | 精品人妻伦一二三区久久| 久久综合九色欧美综合狠狠| 人妻精品久久无码专区精东影业| 久久精品无码一区二区日韩AV| 亚洲中文字幕无码久久2020| 国产亚洲色婷婷久久99精品91| 久久精品国产久精国产果冻传媒 | 久久精品国产99国产精偷| 性做久久久久久久久老女人| 国产韩国精品一区二区三区久久 | 欧美激情精品久久久久久久九九九| 久久青青草原精品国产| 久久久久人妻一区二区三区| 久久精品国产国产精品四凭| 九九99精品久久久久久| 日日噜噜夜夜狠狠久久丁香五月 | 亚洲国产精品久久久天堂| 欧美与黑人午夜性猛交久久久| 99精品伊人久久久大香线蕉| 久久综合精品国产二区无码| 亚洲午夜久久久影院| 精品久久亚洲中文无码| 区久久AAA片69亚洲 | 国产精品欧美亚洲韩国日本久久| 国产亚洲精品美女久久久| 久久综合给合久久国产免费| 久久久亚洲欧洲日产国码二区| 亚洲色大成网站www久久九| 一本一道久久综合狠狠老 |