An -omino is a two-dimensional shape formed by joining unit cells fully along their edges in some way. More formally, a 1-omino is a unit square, and an -omino is an omino with one or more of its edges joined to an adjacent unit square. For the purpose of this problem, we consider two -ominoes to be the same if one can be transformed into the other via reflection and/or rotation. For example, these are the five possible 4-ominoes:
And here are some of the 108 possible 7-ominoes:
Richard and Gabriel are going to play a game with the following rules, for some predetermined values of , , and :
- Richard will choose any one of the possible -ominoes.
- Gabriel must use at least one copy of that -omino, along with arbitrarily many copies of any -ominoes (which can include the one Richard chose), to completely fill in an -by- grid, with no overlaps and no spillover. That is, every cell must be covered by exactly one of the cells making up an -omino, and no -omino can extend outside the grid. Gabriel is allowed to rotate or reflect as many of the -ominoes as he wants, including the one Richard chose. If Gabriel can completely fill in the grid, he wins; otherwise, Richard wins.
Given particular values , , and , can Richard choose an -omino that will ensure that he wins, or is Gabriel guaranteed to win no matter what Richard chooses?
Input Specification
The first line of the input gives the number of test cases, . lines follow. Each contains three space-separated integers: , , and .
Output Specification
For each test case, output one line containing Case #x: y
, where is the test case number (starting from 1) and is either RICHARD
(if there is at least one choice that ensures victory for Richard) or GABRIEL
(if Gabriel will win no matter what Richard chooses).
Limits
Memory limit: 1 GB.
Small dataset
Time limit: 30 seconds.
.
.
Large dataset
Time limit: 60 seconds.
.
.
Sample Input
4
2 2 2
2 1 3
4 4 1
3 2 3
Sample Output
Case #1: GABRIEL
Case #2: RICHARD
Case #3: RICHARD
Case #4: GABRIEL
In case #1, Richard only has one 2-omino available to choose -- the block formed by joining two unit cells together. No matter how Gabriel places this block in the grid, he will leave a hole that can be exactly filled with another block. So Gabriel wins.
In case #2, Richard has to choose the block, but no matter where Gabriel puts it, he will be left with a single hole that he cannot fill using only 2-ominoes. So Richard wins.
In case #3, one winning strategy for Richard is to choose the square 4-omino. There is no way for Gabriel to fit that square into the grid such that it is completely contained within the grid, so Richard wins.
In case #4, Richard can either pick the straight 3-omino or the L-shaped 3-omino. In either case, Gabriel can fit it into the grid and then use another copy of the same 3-omino to fill in the remaining hole.
Note
This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >60.000s
regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.
This problem originally had a much higher time limit. However, as reference solutions were much faster, the Time Limit was been reduced accordingly.
Comments