National Olympiad in Informatics, China, 2000

Day 2, Problem 2 - Frogs Crossing the River

A group of frogs of different sizes stand on a stone pier (labeled A) on the left shore of a river, and would like to cross over to the stone pier on the opposite shore (labeled D). The middle of the river contains several lily pads (labeled Y1 … Ym) and several stepping stones (labeled S1 … Sn). A diagram is as follows:

The rules for the frogs' formation and movements are as follows:

  1. Each frog may only stand on lily pads, stones, or the back of another frog that is one size greater than itself (we shall refer to these as valid landing places).
  2. A frog may only jump from one landing place to another landing place when there are no other frogs on its back.
  3. Frogs are allowed to jump from the left shore's pier A to any stepping stone, lily pad, or the right shore's pier D. Frogs are allowed to jump from any stepping stone or lily pad to the right shore's pier D.
  4. Frogs are allowed to freely jump back and forth between stepping stones and stepping stones, lily pads and lily pads, as well as stepping stones and lily pads.
  5. After a frog leaves the left pier A, it may not return to the left shore. After reaching the right pier D, it may not jump back.
  6. Assume that stone piers and stepping stones can withstand a lot of mass, allowing any number of frogs to stand on them. However due to their area not being too big, there may only be one frog directly standing on top of one, with other frogs standing on its back according to rule number 1.
  7. Not only is the area of a lily pad small like stepping stones, but its weight capacity is also limited. At most one frog may be standing (directly or indirectly) on top of it.
  8. Only one frog may be moved per step, and the rules for frog formation must be followed after each move.
  9. In the beginning, frogs are distributed evenly amongst stone pier A, with the largest frog directly standing on the stone and the remaining frogs standing on the backs of frogs one size greater according to rule number 6.

The frogs wish to eventually be able to all move to D, while maintaining their proper formation.

Let there be m lily pads and n stepping stones. Please find the maximum number of frogs which, under the formation and movement rules, can cross over from A to D.

Ex. When m = 1, n = 1, there contains one lily pad (Y1) and one stepping stone (S1), and there are at most 4 frogs that can cross the river (ordered by size from smallest to largest, labeled 1, 2, 3, 4), one possible way to cross the river is:

Start 
1
2
3
4
A    S1   Y1    D
Step 11 from A to Y1
2
3
4         1
A    S1   Y1    D
Step 22 from A to S1
3
4    2    1
A    S1   Y1    D
Step 31 from Y1 to S1
3    1
4    2
A    S1   Y1    D
Step 43 from A to Y1
     1
4    2    3
A    S1   Y1    D
Step 54 from A to D
     1
     2    3    4
A    S1   Y1    D
Step 63 from Y1 to D
     1         3
     2         4
A    S1   Y1    D
Step 71 from S1 to Y1
               3
     2    1    4
A    S1   Y1    D
Step 82 from S1 to D
               2
               3
          1    4
A    S1   Y1    D
Step 91 from Y1 to D
               1
               2
               3
               4
A    S1   Y1    D

In this example, when there is one lily pad and one stepping stone, 4 frogs can cross over in 9 steps.

Input Format

The input consists of two lines, each containing a single integer. The first line contains n, the number of stepping stones (0 ≤ n ≤ 25). The second line contains the m, the number of lily pads (0 ≤ m ≤ 25).

Output Format

The output should contain one integer, the maximum number of frogs that can cross the river when there are n stepping stones and m lily pads.

Sample Input

1
1

Sample Output

4

All Submissions
Best Solutions


Point Value: 10
Time Limit: 1.00s
Memory Limit: 16M
Added: May 06, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...