a081: NOI2000 Day2.2.青蛙过河
Tags :
Accepted rate : 23人/24人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:27

Content

大小各不相同的一队青蛙站在河左岸的石墩(记为A)上,要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)

图示如下
 

青蛙的站队和移动方法规则如下:

 

1.                        每只青蛙只能站在荷叶、石墩,或者仅比它大一号的青蛙背上(统称为合法的落脚点);

 

2.                        一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点;

 

3.                        青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上,允许从河心的石墩和荷叶跳到右岸的石墩D上;

 

4.                        青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动;

 

5.                        青蛙在离开左岸石墩后,不能再返回左岸;到达右岸后,不能再跳回;

 

6.                        假定石墩承重能力很大,允许无论多少只青蛙都可呆在上面。但是,由于石墩的面积不大,至多只能有一只青蛙直接站在上面,而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。

 

7.                        荷叶不仅面积不大,而且负重能力也有限,至多只能有一只青蛙站在上面。

 

8.                        每一步只能移动一只青蛙,并且移动后需要满足站队规则;

 

9.                        在一开始的时候,青蛙均站在A上,最大的一只青蛙直接站在石墩上,而其它的青蛙依规则6站在比其大一号的青蛙的背上。

 

青蛙希望最终能够全部移动到D上,并完成站队。

 

设河心有m片荷叶和n个石墩,请求出这队青蛙至多有多少只,在满足站队和移动规则的前提下,能从A过到D

 

例如,在m=1 n=1时,河心有一片荷叶(Y1)和一个石墩(S1),此时至多有4只青蛙能够过河(由小到大称为1234),过河的一种方法为:

 

开始 1234A    S1    Y1    D
Step 11 from A to Y1234           1A    S1    Y1    D
Step 22 from A to S134    2     1A    S1    Y1    D
Step 31 from Y1 to S13    14    2A    S1    Y1    D
Step 43 from A to Y1     14    2     3A    S1    Y1    D
Step 54 from A to D     1     2     3     4A    S1    Y1    D
Step 63 from Y1 to D     1           3     2           4A    S1    Y1    D
Step 7 1 from S1 to Y1                 3     2     1     4A    S1    Y1    D
Step 82 from S1 to D23           1     4A    S1    Y1    D
Step 91 from Y1 to D                 1                 2                 3                 4A    S1    Y1    D

此例中,当河心有一片荷叶和一个石墩时,4只青蛙能够跳动9步过河。

Input

文件仅有两行,每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n0<=n<=25),第二行为荷叶数m0<=m<=25)。

Output

文件中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时,最多能够过河的青蛙的只数。

Sample Input
1
1
Sample Output
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :
Tags:
出處:
NOI2000Day2第二题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」