## NOI '00 P5 - Frogs Crossing the River

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 16M

Problem type
##### National Olympiad in Informatics, China, 2000

A group of frogs of different sizes stand on a stone pier (labeled ) on the left shore of a river, and would like to cross over to the stone pier on the opposite shore (labeled ). The middle of the river contains several lily pads (labeled ) and several stepping stones (labeled ). 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 to any stepping stone, lily pad, or the right shore's pier . Frogs are allowed to jump from any stepping stone or lily pad to the right shore's pier .
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 , it may not return to the left shore. After reaching the right pier , 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 , 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 , while maintaining their proper formation.

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

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

 Start Step 1 1 from to Step 2 2 from to Step 3 1 from to Step 4 3 from to Step 5 4 from to Step 6 3 from to Step 7 1 from to Step 8 2 from to Step 9 1 from to

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

#### Input Specification

The input consists of two lines, each containing a single integer. The first line contains , the number of stepping stones . The second line contains the , the number of lily pads .

#### Output Specification

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

#### Sample Input

1
1

#### Sample Output

4

Problem translated to English by Alex.