Problem F
Ocean Monument
Steve has stumbled across an ocean monument and would like
to raid it. He has put on his best set of armor and brought his
favorite trident in search of the rumored sponge room.
The monument is protected by a lot of angry guardians and elder guardians. The mobs are very strong, and Steve has found that each time he enters the monument, he can either kill up to two guardians or exactly one elder guardian before having to retreat to heal. However, each time he retreats, a new guardian spawns in the monument. Luckily, elder guardians never respawn.
Steve will need to slay all the mobs in the monument before
it is safe for him to loot it. He wants to kill the mobs in an
optimal way, such that he minimizes the total number of trips
to the monument required. Write a program that will help him
figure out the number of such optimal orders he can choose
from.
For example, if there were initially
Input
The first line contains an integer
Output
For each test case, output one line containing a single number, the number of optimal orders in which Steve can kill the mobs.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 2 1 5 2 3 |
2 42 14 |