Problem E
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 $1$ guardian and $2$ elder guardians in the monument, there are $2$ optimal orders that minimize the number of trips required: he could either kill an elder guardian in both of the first two trips and kill two guardians in the next two trips, or he could kill an elder guardian in the first trip, kill two guardians in the second trip, kill the second elder guardian in the third trip, and kill two guardians in the fourth trip.
Input
The first line contains an integer $1 \leq t \leq 500$, giving the number of test cases to follow. Each case consists of one line containing two integers $0 \leq g,e \leq 20$, the number of guardians and elder guardians respectively that are in the monument the first time Steve enters.
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 |