A polyomino is a two-dimensional shape formed by putting together some unit squares fully along their edges. An N-omino is a polyomino formed with exactly N unit squares. Two N-ominoes are the same if one can be transformed into the other via reflection and/or rotation.
A rectangular grid of R rows and C columns is also given. Poly's objective is to choose some N-ominoes and tile the grid, i.e. fill the grid without gaps, overlaps, or any part being outside the grid. Omino can choose one N-omino that Poly must use in their tiling. If Poly completes their tiling using Omino's choice, Poly wins; if Poly fails to do so, Omino wins.
Some examples:
- If N = 3 and (R,C) = (3,2), Omino's two possible choices are I- and L-tromino. In both cases, Poly can tile a 3x2 grid using two copies of Omino's choice, so Poly wins.
- If N = 4 and (R,C) = (1,4), Omino can choose any tetromino that is not an I. Poly has no way to fit it in the grid that is too narrow, so Omino wins.
For each possible value of N, R, and C, determine who will win, assuming both players play optimally.
Source: Google Code Jam 2015, Qualification Round, Problem D