(2)任意一段連續(xù)的子串沒有連續(xù)出現(xiàn)3次(如：010101、001001001就不符合要求)

　　輸入

　　輸入僅一個(gè)數(shù)，即序列長度

　　輸出

　　輸出僅一個(gè)數(shù)，即滿足要求的序列總數(shù)

　　Problem9生日蛋糕

　　題目描述

　　要制作一個(gè)體積為N*pi的M層生日蛋糕，每層都是一個(gè)圓柱體。 設(shè)從下往上數(shù)第i(1 <= i <= M)層蛋糕是半徑為Ri, 高度為Hi的圓柱。當(dāng)i < M時(shí)，要求Ri > Ri+1且Hi > Hi+1。 由于要在蛋糕上抹奶油，為盡可能節(jié)約經(jīng)費(fèi)，我們希望蛋糕外表面（最下一層的下底面除外）的面積Q最小。 令Q = S*pi 請編程對給出的N和M，找出蛋糕的制作方案（適當(dāng)?shù)腞i和Hi的值），使S最小。（除Q外，以上所有數(shù)據(jù)皆為正整數(shù)）

　　輸入

　　輸入兩行，第一行為N（N <= 10000），表示待制作的蛋糕的體積為N*pi；第二行為M(M <= 20)，表示蛋糕的層數(shù)為M。

　　輸出

　　輸出僅一行，是一個(gè)正整數(shù)S（若無解則S=0）。

　　四、 圖論算法

　　Problem1一筆畫問題

　　題目描述

　　給出一個(gè)圖，求其歐拉回路（若沒有回路，則求其歐拉路徑），若不存在則輸出'No solution'

　　輸入

　　輸入的第一行為邊數(shù)F(<=1024)，后面F行每行表示一條邊（定點(diǎn)標(biāo)號(hào)范圍為1-500）

　　輸出

　　輸出一條合法的歐拉回路（路徑），若有多條滿足要求，輸出其字典序最小的那一個(gè)。

　　Problem2 Car的旅行路線

　　題目描述

　　住在城市A的Car想和朋友一起去城市B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市中兩個(gè)機(jī)場之間有一條筆直的高速鐵路，第I個(gè)城市中高速鐵路了的單位里程價(jià)格為Ti，任意兩個(gè)不同城市的機(jī)場之間均有航線，所有航線單位里程的價(jià)格均為t。

　　那么Car應(yīng)如何安排到城市B的路線才能盡可能的節(jié)省花費(fèi)，求其最少花費(fèi)

　　輸入

　　第一行有四個(gè)正整數(shù)s，t，A，B。

　　S(0<S<=100)表示城市的個(gè)數(shù)，t表示飛機(jī)單位里程的價(jià)格，A，B分別為城市A，B的序號(hào)，(1<=A，B<=S)。

　　接下來有S行，其中第I行均有7個(gè)正整數(shù)xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當(dāng)中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第I個(gè)城市中任意三個(gè)機(jī)場的坐標(biāo)，T I為第I個(gè)城市高速鐵路單位里程的價(jià)格。

　　輸出

　　輸出最小花費(fèi)，保留一位小數(shù)

　　Problem3求割點(diǎn)與橋

　　題目描述

　　給定一個(gè)圖，求其割點(diǎn)與橋

　　輸入

　　第一行有兩個(gè)整數(shù)，n、e，即點(diǎn)數(shù)與邊數(shù)

　　后面e行，每行兩個(gè)整數(shù)v1、v2，表示點(diǎn)v1與v2相連

　　輸出

　　首先輸出所有割點(diǎn)，每行輸出一個(gè)

　　然后輸出所有橋，每行一條

　　(不用考慮順序)

　　Problem4十字繡

　　題目描述

　　布是一個(gè)n*m的網(wǎng)格，線只能在網(wǎng)格的頂點(diǎn)處才能從布的一面穿到另一面。每一段線都覆蓋一個(gè)單位網(wǎng)格的兩條對角線之一，而在繡的過程中，一針中連續(xù)的兩段線必須分處布的兩面。給出布兩面的圖案(實(shí)線代表該處有線,虛線代表背面有線)，問最少需要幾針才能繡出來？一針是指針不離開布的一次繡花過程。

　　輸入

　　輸入第1行兩個(gè)數(shù)N和M(1<=N,M<=200)。

　　接下來N行每行M個(gè)數(shù)描述正面。

　　再接下來N行每行M個(gè)數(shù)描述反面。

　　每個(gè)格子用.（表示空）,/（表示從右上角連到左下角）,\（表示從左上角連到右下角）和X（表示連兩條對角線）表示。

　　輸出

　　輸出一個(gè)數(shù)，最少要用的針數(shù)

　　Problem5舞會(huì)

　　題目描述

　　一個(gè)舞會(huì)邀請n個(gè)人，這n個(gè)人每一個(gè)人都有一個(gè)小花名冊，名冊里面寫著他所愿意交流的人的名字。比如說在A的人名單里寫了B，那么表示A愿意與B交流；但是B的名單里不見的有A，也就是說B不見的想與A交流。但是如果A愿意與B交流，B愿意與C交流，那么A一定愿意與C交流。也就是說交流有傳遞性�，F(xiàn)在覺得需要將這n個(gè)人分為m組，要求每一組的任何一人都愿意與組內(nèi)其他人交流。并求出一種方案以確定m的最小值是多少。

　　注意：自己的名單里面不會(huì)有自己的名字。

　　輸入

　　輸入第一行一個(gè)數(shù)n。接下來n行，每i+1行表示編號(hào)為i的人的小花名冊名單，名單以0結(jié)束。1<=n<=200。

　　輸出

　　輸出即m的最小值

　　Problem6休息中的小呆

　　題目描述

　　NOIP備戰(zhàn)之際，小呆正在悠閑（欠扁）地玩一個(gè)叫"最初夢想"的游戲。游戲描述的是一個(gè)叫pass的有志少年在不同的時(shí)空穿越對抗傳說中的大魔王chinesesonic的故事。小呆發(fā)現(xiàn)這個(gè)游戲的故事流程設(shè)計(jì)得很復(fù)雜，它有著很多的分支劇情，但不同的分支劇情是可以同時(shí)進(jìn)行的，因此游戲可以由劇情和劇情的結(jié)束點(diǎn)組成，某些劇情必須要在一些特定的劇情結(jié)束后才能繼續(xù)發(fā)展。為了體驗(yàn)游戲的完整性，小呆決定要看到所有的分支劇情--完成所有的任務(wù)。但這樣做會(huì)不會(huì)耽誤小呆寶貴的睡覺時(shí)間呢？所以就請你來解決這個(gè)問題了。

　　輸入

　　輸入會(huì)給你一個(gè)劇情流程和完成條件的列表，其中第一行有一個(gè)數(shù)n（0<n<100），表示總共有n個(gè)劇情結(jié)束點(diǎn)，第二行一個(gè)數(shù)m(0<m<=120)，表示由m個(gè)不同的劇情，下面的m行中每行有三個(gè)數(shù)i0<i<=100),j0<j<=100),k0<k<=1000)，表示從劇情結(jié)束點(diǎn)i必須完成一個(gè)耗費(fèi)時(shí)間為k的劇情才能到達(dá)劇情結(jié)束點(diǎn)j。注意，這m行中出現(xiàn)的1不是劇情結(jié)束點(diǎn)而是游戲的開始，而n+1表示游戲結(jié)束。

　　輸出

　　輸出第一行為一個(gè)數(shù)，即你要告訴小呆完成整個(gè)游戲至少需要多少時(shí)間，第二韓有若干個(gè)數(shù)，即要經(jīng)過的所有可能的劇情結(jié)束點(diǎn)（按升序輸出）。

　　Problem7最優(yōu)布線問題

　　題目描述

　　校園里有n臺(tái)計(jì)算機(jī)，要將它們用數(shù)據(jù)線連接起來。由于計(jì)算機(jī)所處的位置不同，連接2臺(tái)計(jì)算機(jī)的費(fèi)用往往是不同的。如果將每2 臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接，勢必造成浪費(fèi)。為了節(jié)省費(fèi)用，可以采用數(shù)據(jù)的間接傳輸手段，即一臺(tái)計(jì)算機(jī)可以間接通過若干臺(tái)計(jì)算機(jī)(作為中轉(zhuǎn))來實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接。如何用最少費(fèi)用連接n臺(tái)計(jì)算機(jī)。

　　輸入

　　輸入數(shù)據(jù)。第一行有1個(gè)正整數(shù)n，表示計(jì)算機(jī)數(shù)。此后n行，每行有n個(gè)正整數(shù)。第x+1行，第y列的正整數(shù)表示直接連接第x臺(tái)計(jì)算機(jī)和第y臺(tái)計(jì)算機(jī)的費(fèi)用。

　　輸出

　　輸出最小費(fèi)用

　　Problem8磁盤碎片整理

　　題目描述

　　出于最高安全性考慮，司令部采用了特殊的安全操作系統(tǒng)。該系統(tǒng)采用一個(gè)特殊的文件系統(tǒng)。在這個(gè)文件系統(tǒng)中所有磁盤空間都被分配了相同尺寸的N塊，用整數(shù)1到N表識(shí)，每個(gè)文件占用磁盤上任意區(qū)域的一塊或多塊存儲(chǔ)區(qū)，未被文件占用的存儲(chǔ)塊被認(rèn)為是可以使用的。如果文件存儲(chǔ)在磁盤上自然連續(xù)的存儲(chǔ)塊中，則能被以最快的速度讀出。

　　因?yàn)榇疟P是均勻轉(zhuǎn)動(dòng)的，所以存取上面的不同的存儲(chǔ)快需要的時(shí)間也不同。讀取磁盤開頭處的存儲(chǔ)比讀取磁盤結(jié)尾處的存儲(chǔ)塊快。根據(jù)以上現(xiàn)象，我們事先將文件按其存取頻率的大小用整數(shù)1到K標(biāo)識(shí)。按文件在磁盤上最佳的存儲(chǔ)方法，1號(hào)文件將占用1，2……，S1的存儲(chǔ)塊，2號(hào)文件占用S1+1,S1+2……S1+S2的存儲(chǔ)塊，依次類推。為了將文件以最佳形式存儲(chǔ)在磁盤上，需要執(zhí)行存儲(chǔ)酷塊移動(dòng)操作。操作后，原空間將被釋放，新空間將被占用。

　　問對于一個(gè)文件序列，最少需要多少次移動(dòng)操作才能以最佳方式存儲(chǔ)到磁盤上

　　輸入

　　輸入第一行包含兩個(gè)整數(shù)N，K，接下來K行每行描述一個(gè)文件，第一個(gè)數(shù)為Si，表示其存儲(chǔ)塊數(shù)量，后面有Si個(gè)整數(shù)，每個(gè)整數(shù)之間用空格隔開，表示該文件按自然順序在磁盤上占用的存儲(chǔ)塊標(biāo)識(shí)，所有這些數(shù)都介于1和N之間，包括1和N。

　　所有磁盤空間的表識(shí)都不相同

　　輸出

　　輸出一個(gè)數(shù)，即最小移動(dòng)次數(shù)

　　Problem9說謊島

　　題目描述

　　哥侖布在到達(dá)美州后，發(fā)現(xiàn)了一個(gè)奇特的島嶼。這個(gè)島嶼上的人狡猾且喜歡說謊，由于完全的謊言較易為人所識(shí)破，所以為了更加能夠迷惑別人，他們的言語往往是半真半假的。

　　由于對于環(huán)境的不熟悉，哥侖布有許多問題要請教島上的居民。當(dāng)然他已經(jīng)知道了島上居民的這一說謊習(xí)俗。

　　幸好，哥侖布的所有問題都只需回答"是"或者"否"，這樣便免去了許多繁復(fù)。假設(shè)哥侖布詢問了N個(gè)居民，對于每個(gè)居民只問兩個(gè)問題，每個(gè)居民只需對于每個(gè)問題回答"是"或"否"。根據(jù)居民的習(xí)俗，可以斷定兩個(gè)回答中必有一個(gè)是正確的，而另一個(gè)是錯(cuò)誤的。同一個(gè)問題可以反復(fù)問多人。

　　哥侖布根據(jù)這N個(gè)人的回答，需要整理推斷出他所有問題的答案。但這一過程實(shí)在太復(fù)雜與困難了，因此希望你能夠編程求出所有可能答案的種數(shù)。

　　輸入

　　輸入第一行是兩個(gè)整數(shù)N（1≤N≤10000）、M（1≤M≤200），以空格分隔。分別表示詢問了N人，共有M個(gè)問題。整個(gè)輸入文件共N+1行。

　　第i+1行共有四個(gè)整數(shù)a,b,c,d，以空格分隔。表示第i個(gè)人對于第a個(gè)問題的答案是b, 對于第c個(gè)問題的答案是d。其中1≤a,c≤M。b和d為0時(shí)表示答案為"否；"為1時(shí)表示答案為"是"。

　　輸出

　　若不可能推出任何結(jié)果，即無解，輸出"NO ANSWER"；否則輸出可能答案組的個(gè)數(shù)。

　　Problem10 01串問題

　　題目描述

　　給定7個(gè)整數(shù)N,A0,B0,L0,A1,B1,L1，要求設(shè)計(jì)一個(gè)01串S=s1s2…si…sN，滿足：

　　1.si=0或si=1，1<=i<=N；

　　2.對于S的任何連續(xù)的長度為L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1)，0的個(gè)數(shù)大于等于A0且小于等于B0;

　　3.對于S的任何連續(xù)的長度為L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1)，1的個(gè)數(shù)大于等于A1且小于等于B1;

　　例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，則存在一個(gè)滿足上述所有條件的01串S=010101。

　　輸入

　　輸入僅一行，有7個(gè)整數(shù)，依次表示N,A0,B0,L0,A1,B1,L1（3<=N<=1000，1<= A0<=B0<=L0<=N，1<=A1<=B1<=L1<=N），相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

　　輸出

　　輸出僅一行，若不存在滿足所有條件的01串，則輸出一個(gè)整數(shù)-1，否則輸出一個(gè)滿足所有條件的01串。

　　Problem11海島地圖

　　題目描述

　　給出一個(gè)(h*w)的海島地圖，其中圖中1表示陸地，0表示水域，求所有島嶼中，面積最大的一個(gè)島嶼

　　輸入

　　輸入第一行為w，h(<=100)，表示圖的長與寬

　　后面有w行，每行有一個(gè)長為h的01串，用來描述整個(gè)地圖

　　輸出

　　輸出僅一個(gè)數(shù)，即最大的海島面積

　　五、 數(shù)學(xué)問題

　　Problem1數(shù)的劃分

　　題目描述

　　將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。

　　例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。

　　1，1，5; 1，5，1; 5，1，1;

　　問有多少種不同的分法。

　　輸入

　　輸入僅一行，即N，K(N<=200,K<=20)

　　輸出

　　輸出僅一個(gè)數(shù)，即總共的方法數(shù)

　　Problem2最優(yōu)分解方案

　　題目描述

　　給定整數(shù)N，將其分解為若干個(gè)互不相同的整數(shù)，是他們的乘積最大

　　輸入

　　輸入僅一個(gè)數(shù)，N(N<=1000)

　　輸出

　　輸出最大乘積

　　Problem3出棧序列統(tǒng)計(jì)

　　題目描述

　　棧是常用的一種數(shù)據(jù)結(jié)構(gòu),有n令元素在棧頂端一側(cè)等待進(jìn)棧,棧頂端另一側(cè)是出棧序列.你已經(jīng)知道棧的操作有兩·種:push和pop,前者是將一個(gè)元素進(jìn)棧,后者是將棧頂元素彈出.現(xiàn)在要使用這兩種操作,由一個(gè)操作序列可以得到一系列的輸出序列.請你編程求出對于給定的n,計(jì)算并輸出由操作數(shù)序列1,2,…,n,經(jīng)過一系列操作可能得到的輸出序列總數(shù).

　　輸入

　　輸入一個(gè)整數(shù)n(1<=n<=50)

　　輸出

　　輸出一個(gè)整數(shù)，即可能輸出序列的總數(shù)目。

　　Problem4百事世界杯之旅

　　題目描述

　　每個(gè)瓶蓋上有一個(gè)球星的名字，有N個(gè)不同的球星，平均情況下，要買多少瓶飲料才能集齊所有名字

　　輸入

　　輸入一個(gè)數(shù)N(<=33)

　　輸出

　　輸出平均情況下的瓶數(shù)，若為整數(shù)則直接輸出，若為分?jǐn)?shù)，則以真分?jǐn)?shù)形式輸出，格式如下：

　　b

　　a-

　　c

　　Problem5電子鎖

　　題目描述

　　某機(jī)要部門安裝了電子鎖。m個(gè)工作人員每人發(fā)一張磁卡，卡上有開鎖的密碼特征，為了保證安全，規(guī)定至少n個(gè)人同時(shí)使用各自的磁卡才能將鎖打開。現(xiàn)在需要你計(jì)算一下，電子鎖上至少要有多少種特征，每個(gè)人的磁卡上至少要有幾種特征。同時(shí)輸出分配方案。

　　輸入

　　輸入僅一行，有兩個(gè)數(shù)即m(m<=7)，n(<=m且<=4)

　　輸出

　　輸出第一行為兩個(gè)數(shù)，既電子鎖上的特征數(shù)，與磁卡上的特征數(shù)

　　后面n行按字典序數(shù)出一個(gè)01序列，表識(shí)每個(gè)人磁卡上的擁有的特征，1表識(shí)有，0表示沒有。

　　Problem6堆塔問題

　　題目描述

　　有n個(gè)邊長為一的正立方體，在一個(gè)寬為1的軌道上堆塔，但它本身不能分離。

　　堆塔時(shí)底層必須有支撐，求對于n各正方體，又多少種方案

　　輸入

　　輸入僅一行n(n<=100)

　　輸出

　　輸出也只一行，即總方案數(shù)

　　Problem7取數(shù)游戲

　　題目描述

　　給出正整數(shù)n(<=1000000)和k(<n)，然后按下列方法取數(shù):(n=16,k=4)

　　1: 取1  剩 15

　　2: 取2  剩 13

　　3: 取4  剩 9

　　4: 取8  剩 1

　　第五次取不夠，加上k個(gè)，現(xiàn)在共5個(gè)

　　5: 取1  剩 4

　　6: 取2  剩 2

　　第七次取不夠，加上k個(gè)，現(xiàn)在共6個(gè)

　　7: 取1  剩 5

　　8: 取2  剩 3

　　第九次取不夠，加上k個(gè)，現(xiàn)在共7個(gè)

　　9: 取1  剩 6

　　10: 取1  剩 4

　　11: 取1  剩 0

　　取完共取11次

　　輸入

　　輸入僅一行，即n，k

　　輸出

　　若取得完，則輸出取的次數(shù)，否則輸出'Error'

　　Problem8球迷購票

　　題目描述

　　球迷手上有100元與50元的鈔票，每張票50元，現(xiàn)在有m+n個(gè)球迷買票(m個(gè)手上持50元的，n個(gè)手上持100元的)，一開始售票員手上有錢，有多少排隊(duì)方案可以不出現(xiàn)沒有錢找的局面

　　輸入

　　輸入僅一行即m，n(m,n<=5000)

　　輸出

　　輸出有一行，即總得方案數(shù)

　　Problem9 Fibonacci公約數(shù)

　　題目描述

　　給出兩個(gè)fibonacci數(shù)，求一個(gè)最大的fibonacci數(shù)，滿足這個(gè)數(shù)是他們的最大公約數(shù)

　　輸入

　　輸入有兩行，分別是兩個(gè)Fibonacci數(shù)(<=10^2000)

　　輸出

　　即輸出他們的Fibonacci公約數(shù)

　　Problem10傳球問題

　　題目描述

　　Grant老師常和小朋友們一起玩一種傳球游戲。游戲是這樣進(jìn)行的：

　　一群小朋友分成兩組，每組n人，圍成一個(gè)圈。每一個(gè)小朋友都有一個(gè)編號(hào)(1..n之間)，這個(gè)編號(hào)在其所在組中是唯一的。    游戲開始之前，Grant老師會(huì)發(fā)給每個(gè)小朋友一個(gè)球，球上也有編號(hào)(1..n之間)，并且一個(gè)組中的球不會(huì)有兩個(gè)相同編號(hào)。然后，所有小朋友必須閉上眼睛，游戲開始。隨著Grant老師口中的哨子發(fā)出的節(jié)奏，每個(gè)小朋友都用一只手把球傳到右邊，而用另一只手接左邊的來球。

　　突然，Grant老師的哨子停了，關(guān)鍵的時(shí)刻到了。小朋友馬上睜開眼睛，開始與同組的小朋友之間進(jìn)行傳球，爭取以最短的時(shí)間把球傳到位。傳到位是指一個(gè)組中的每一個(gè)小朋友手上的球的編號(hào)與他自己的編號(hào)相同。最后獲勝的就是那個(gè)最先把球傳到位的組。如果一旦哪方出現(xiàn)傳球失誤(球沒被接到而落地)，或犯規(guī)（一個(gè)人手上拿兩個(gè)或兩個(gè)以上的球）這一組就被判輸。

　　這個(gè)游戲非常有趣，小朋友們玩了許多次。他們總結(jié)出一條經(jīng)驗(yàn)：總是兩個(gè)人之間對傳。也就是說，不會(huì)出現(xiàn)a把球傳給b，而b沒有把球傳給a的這種情況。這樣可以避免小朋友之間的失誤與犯規(guī)。不過還有個(gè)關(guān)鍵問題就是怎么傳。究竟應(yīng)該把手上的球傳給誰？

　　現(xiàn)在需要你編一個(gè)程序來幫助小朋友們確定傳球方法。你的程序首先需要計(jì)算出從一種初始狀態(tài)開始：

　　子問題 1：至少需要幾次對傳才能將球傳到位。

　　子問題2：至少需要多少時(shí)間才能將球傳到位。每一個(gè)時(shí)間單位一個(gè)小朋友可以不做任何動(dòng)作，也可以與另外一個(gè)小朋友之                 間進(jìn)行對傳。

　　注意有些對傳可以同時(shí)進(jìn)行。比如小朋友1與小朋友2之間的對傳和小朋友3與小朋友4之間的對傳就可以在一個(gè)時(shí)間單位之內(nèi)完成，但是被計(jì)作兩次對傳。

　　輸入：

　　輸入第一行是一個(gè)整數(shù) n (2<=n<=20000)。接下來有n 行，每行一個(gè)整數(shù)(1..n)，其中第(i+1)行的整數(shù)表示i號(hào)小朋友手上的球的編號(hào)。

　　輸出：

　　輸出只有二行，每行一個(gè)整數(shù)，分別表示子問題1和子問題2的解。

　　Problem11約瑟夫問題

　　題目描述

　　n個(gè)人排成一圈。從某個(gè)人開始，按順時(shí)針方向依次編號(hào)。從編號(hào)為1的人開始順時(shí)針"一二一"報(bào)數(shù)，報(bào)到2的人退出圈子。這樣不斷循環(huán)下去，圈子里的人將不斷減少。由于人的個(gè)數(shù)是有限的，因此最終會(huì)剩下一個(gè)人。試問最后剩下的人最開始的編號(hào)。

　　輸入

　　輸入一個(gè)正整數(shù)n，表示人的個(gè)數(shù)。輸入數(shù)據(jù)保證數(shù)字n不超過100位。

　　輸出

　　輸出一個(gè)正整數(shù)。它表示經(jīng)過"一二一"報(bào)數(shù)后最后剩下的人的編號(hào)。

　　Problem12青蛙過河

　　題目描述

　　大小各不相同的一隊(duì)青蛙站在河左岸的石墩（記為A）上，要過到對岸的石墩(記為D)上去。河心有幾片菏葉(分別記為Y1…Ym)和幾個(gè)石墩(分別記為S1…Sn)。

　　青蛙的站隊(duì)和移動(dòng)方法規(guī)則如下：

　　1．每只青蛙只能站在荷葉、石墩，或者僅比它大一號(hào)的青蛙背上（統(tǒng)稱為合法的落腳點(diǎn)）；

　　2．一只青蛙只有背上沒有其它青蛙的時(shí)候才能夠從一個(gè)落腳點(diǎn)跳到另一個(gè)落腳點(diǎn)；

　　3．青蛙允許從左岸A直接跳到河心的石墩、荷葉和右岸的石墩D上，允許從河心的石墩和荷葉跳到右岸的石墩D上；

　　4．青蛙在河心的石墩之間、荷葉之間以及石墩和荷葉之間可以來回跳動(dòng)；

　　5．青蛙在離開左岸石墩后，不能再返回左岸；到達(dá)右岸后，不能再跳回；

　　6．假定石墩承重能力很大，允許無論多少只青蛙都可呆在上面。但是，由于石墩的面積不大，至多只能有一只青蛙直接站在上       面，而其他的青蛙只能依規(guī)則1落在比它大一號(hào)的青蛙的背上。

　　7．荷葉不僅面積不大，而且負(fù)重能力也有限，至多只能有一只青蛙站在上面。

　　8．每一步只能移動(dòng)一只青蛙，并且移動(dòng)后需要滿足站隊(duì)規(guī)則；

　　9．在一開始的時(shí)候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依規(guī)則6站在比其大一號(hào)的青蛙的背上。

　　青蛙希望最終能夠全部移動(dòng)到D上，并完成站隊(duì)。

　　設(shè)河心有m片荷葉和n個(gè)石墩，請求出這隊(duì)青蛙至多有多少只，在滿足站隊(duì)和移動(dòng)規(guī)則的前提下，能從A過到D。

　　輸入

　　輸入僅有兩行，每一行僅包含一個(gè)整數(shù)和一個(gè)換行/回車符。第一行的數(shù)字為河心的石墩數(shù)n（0<=n<=25），第二行為荷葉數(shù)m（0<=m<=25）。

　　輸出

　　輸出中僅包含一個(gè)數(shù)字和一個(gè)換行/回車符。該數(shù)字為在河心有n個(gè)石墩和m片荷葉時(shí)，最多能夠過河的青蛙的只數(shù)。

　　Problem13棋盤游戲

　　題目描述

　　大小為3的棋盤游戲里有3個(gè)白色棋子，3個(gè)黑色棋子，和一個(gè)有7個(gè)格子一線排開的木盒子。3個(gè)白棋子被放在一頭，3個(gè)黑棋子被放在另一頭，中間的格子空著。

　　初始狀態(tài): WWW_BBB

　　目標(biāo)狀態(tài): BBB_WWW

　　在這個(gè)游戲里有兩種移動(dòng)方法是允許的：

　　1. 你可以把一個(gè)棋子移到與它相鄰的空格；

　　2. 你可以把一個(gè)棋子跳過一個(gè)(僅一個(gè))與它不同色的棋子到達(dá)空格。

　　大小為N的棋盤游戲包括N個(gè)白棋子，N個(gè)黑棋子，還有有2N+1個(gè)格子的木盒子。

　　這里是3-棋盤游戲的解，包括初始狀態(tài)，中間狀態(tài)和目標(biāo)狀態(tài)：

　　WWW BBB

　　WW WBBB

　　WWBW BB

　　WWBWB B

　　WWB BWB

　　W BWBWB

　　WBWBWB

　　BW WBWB

　　BWBW WB

　　BWBWBW

　　BWBWB W

　　BWB BWW

　　B BWBWW

　　BB WBWW

　　BBBW WW

　　BBB WWW