[HomeTrainingProblemsContestsC Language]  [LoginRegister] 
Problems Status Rank 
Problem 1049
Ominous Omino
Time Limit: 1000ms
Memory Limit: 65536kb Description
An Nomino is a twodimensional shape formed by joining N unit cells fully along their edges in some way. More formally, a 1omino is a 1x1 unit square, and an Nomino is an (N1)omino with one or more of its edges joined to an adjacent 1x1 unit square. For the purpose of this problem, we consider two Nominoes to be the same if one can be transformed into the other via reflection and/or rotation. For example, these are the five possible 4ominoes:And here are some of the 108 possible 7ominoes: Richard and Gabriel are going to play a game with the following rules, for some predetermined values of X, R, and C: 1. Richard will choose any one of the possible Xominoes. 2. Gabriel must use at least one copy of that Xomino, along with arbitrarily many copies of any Xominoes (which can include the one Richard chose), to completely fill in an RbyC grid, with no overlaps and no spillover. That is, every cell must be covered by exactly one of the X cells making up an Xomino, and no Xomino can extend outside the grid. Gabriel is allowed to rotate or reflect as many of the Xominoes as he wants, including the one Richard chose. If Gabriel can completely fill in the grid, he wins; otherwise, Richard wins. Given particular values X, R, and C, can Richard choose an Xomino that will ensure that he wins, or is Gabriel guaranteed to win no matter what Richard chooses? Input
The first line of the input gives the number of test cases, T. T lines follow. Each contains three spaceseparated integers: X, R, and C.1 ≤ T ≤ 100. 1 ≤ X, R, C ≤ 20. Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y 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).
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 Hint
In case #1, Richard only has one 2omino available to choose  the 1x2 block formed by joining two unit cells together. No matter how Gabriel places this block in the 2x2 grid, he will leave a hole that can be exactly filled with another 1x2 block. So Gabriel wins.In case #2, Richard has to choose the 1x2 block, but no matter where Gabriel puts it, he will be left with a single 1x1 hole that he cannot fill using only 2ominoes. So Richard wins. In case #3, one winning strategy for Richard is to choose the 2x2 square 4omino. There is no way for Gabriel to fit that square into the 4x1 grid such that it is completely contained within the grid, so Richard wins. In case #4, Richard can either pick the straight 3omino or the Lshaped 3omino. In either case, Gabriel can fit it into the grid and then use another copy of the same 3omino to fill in the remaining hole. Source
Google Code Jam 2015 Qualification Round
