信息學(xué)聯(lián)賽知識：基本程序題集(3)

(2)任意一段連續的子串沒(méi)有連續出現3次(如：010101、001001001就不符合要求)

　　輸入

　　輸入僅一個(gè)數，即序列長(cháng)度

　　輸出

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

　　Problem9生日蛋糕

　　題目描述

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

　　輸入

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

　　輸出

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

　　四、 圖論算法

　　Problem1一筆畫(huà)問(wèn)題

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem2 Car的旅行路線(xiàn)

　　題目描述

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

　　那么Car應如何安排到城市B的路線(xiàn)才能盡可能的節省花費，求其最少花費

　　輸入

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

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

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

　　輸出

　　輸出最小花費，保留一位小數

　　Problem3求割點(diǎn)與橋

　　題目描述

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

　　輸入

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

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

　　輸出

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

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

　　(不用考慮順序)

　　Problem4十字繡

　　題目描述

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

　　輸入

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

　　接下來(lái)N行每行M個(gè)數描述正面。

　　再接下來(lái)N行每行M個(gè)數描述反面。

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

　　輸出

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

　　Problem5舞會(huì )

　　題目描述

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

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

　　輸入

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

　　輸出

　　輸出即m的最小值

　　Problem6休息中的小呆

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem7最優(yōu)布線(xiàn)問(wèn)題

　　題目描述

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

　　輸入

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

　　輸出

　　輸出最小費用

　　Problem8磁盤(pán)碎片整理

　　題目描述

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

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

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

　　輸入

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

　　所有磁盤(pán)空間的表識都不相同

　　輸出

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

　　Problem9說(shuō)謊島

　　題目描述

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

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

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

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

　　輸入

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

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

　　輸出

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

　　Problem10 01串問(wèn)題

　　題目描述

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

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

　　2.對于S的任何連續的長(cháng)度為L(cháng)0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1)，0的個(gè)數大于等于A(yíng)0且小于等于B0;

　　3.對于S的任何連續的長(cháng)度為L(cháng)1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1)，1的個(gè)數大于等于A(yíng)1且小于等于B1;

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

　　輸入

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

　　輸出

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

　　Problem11海島地圖

　　題目描述

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

　　輸入

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

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

　　輸出

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

　　五、 數學(xué)問(wèn)題

　　Problem1數的劃分

　　題目描述

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

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

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

　　問(wèn)有多少種不同的分法。

　　輸入

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

　　輸出

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

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

　　題目描述

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

　　輸入

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

　　輸出

　　輸出最大乘積

　　Problem3出棧序列統計

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem4百事世界杯之旅

　　題目描述

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

　　輸入

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

　　輸出

　　輸出平均情況下的瓶數，若為整數則直接輸出，若為分數，則以真分數形式輸出，格式如下：

　　b

　　a-

　　c

　　Problem5電子鎖

　　題目描述

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

　　輸入

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

　　輸出

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

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

　　Problem6堆塔問(wèn)題

　　題目描述

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

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

　　輸入

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

　　輸出

　　輸出也只一行，即總方案數

　　Problem7取數游戲

　　題目描述

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

　　1: 取1  剩 15

　　2: 取2  剩 13

　　3: 取4  剩 9

　　4: 取8  剩 1

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

　　5: 取1  剩 4

　　6: 取2  剩 2

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

　　7: 取1  剩 5

　　8: 取2  剩 3

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

　　9: 取1  剩 6

　　10: 取1  剩 4

　　11: 取1  剩 0

　　取完共取11次

　　輸入

　　輸入僅一行，即n，k

　　輸出

　　若取得完，則輸出取的次數，否則輸出'Error'

　　Problem8球迷購票

　　題目描述

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

　　輸入

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

　　輸出

　　輸出有一行，即總得方案數

　　Problem9 Fibonacci公約數

　　題目描述

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

　　輸入

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

　　輸出

　　即輸出他們的Fibonacci公約數

　　Problem10傳球問(wèn)題

　　題目描述

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

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

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

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

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

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

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

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

　　輸入：

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

　　輸出：

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

　　Problem11約瑟夫問(wèn)題

　　題目描述

　　n個(gè)人排成一圈。從某個(gè)人開(kāi)始，按順時(shí)針?lè )较蛞来尉幪�。從編號�?的人開(kāi)始順時(shí)針"一二一"報數，報到2的人退出圈子。這樣不斷循環(huán)下去，圈子里的人將不斷減少。由于人的個(gè)數是有限的，因此最終會(huì )剩下一個(gè)人。試問(wèn)最后剩下的人最開(kāi)始的編號。

　　輸入

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

　　輸出

　　輸出一個(gè)正整數。它表示經(jīng)過(guò)"一二一"報數后最后剩下的人的編號。

　　Problem12青蛙過(guò)河

　　題目描述

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

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

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

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

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

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

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

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

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

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

　　9．在一開(kāi)始的時(shí)候，青蛙均站在A(yíng)上，最大的一只青蛙直接站在石墩上，而其它的青蛙依規則6站在比其大一號的青蛙的背上。

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

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

　　輸入

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

　　輸出

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

　　Problem13棋盤(pán)游戲

　　題目描述

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

　　初始狀態(tài): WWW_BBB

　　目標狀態(tài): BBB_WWW

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

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

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

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

　　這里是3-棋盤(pán)游戲的解，包括初始狀態(tài)，中間狀態(tài)和目標狀態(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