908 . Risk
TopCoder
Description
Risk is a turn-based game for two to six players. The standard version is played on a board depicting a political map of the Earth, divided into forty-two territories, which are grouped into six continents. Players attempt to capture territories from other players by rolling higher die numbers. The game is won when one player has managed to occupy every territory.
KerkerKnight is the ruler of Asia continent, and decided to train a kind of elite troop to aid his conquest over the world. The name of the troop is:
" GOODKNIGHT "
As its name suggests, it is a very good knight, which is so powerful that even gunpowder could not penetrate it, even the greatest fortress are vulnerable to it. However, with only one drawback - due to some innate disability, GOODKNIGHTS move in only certain ways (just as chess knights do!!).
Consider the world as a grid with the GOODKNIGHT placed in the origin, it could only make limited moves that could be described by vectors (with integer indices).
For example, a GOODKNIGHT may be able to make a set of move: {(1,3), (2,2), (-2,-1)}. By (1,3) it suggests that the GOODKNIGHT can move to the point (1,3) and also (-1,-3). Of course, the GOODKNIGHT can also makes a combination of moves to reach some other points, such as it could take the move (1,3) two times to reach (2,6), or to go (-2,-1) followed by (-2,-2) to reach (-4,-3).
Now, given all the possible moves the GOODKNIGHT could make, and a sequence of destinations of concern, determine whether each destination is reachable for the GOODKNIGHT.
Input Format
The first line of input consists of an integer T: the number of testcases.
For each testcase, the first line contains a number N: the number of moves for the GOODKNIGHT
in the following N lines each line consists of a pair of integer, the vector that represents a valid move of GOODKNIGHT
After the moves, an integer Q follows: the number of queries,
Q lines then follow, each contain a pair of integer representing the coordinate of the destination of concern.
Output Format
For each queries, print a single line.
Output "kerkerknight rules" if the destination is reachable for the GOODKNIGHT,
otherwise output "kerbowen rules".
1 <= T <= 100
1 <= N <= 100000
1 <= Q <= 100000
|value of the coordinates| <= 10000000
Sample Input 1
2 2 1 2 2 1 7 -1 1 7 -7 100 0 77 0 0 96 0 33 2 40 5 1 2 9 100 2 1 -9 -99 2 1 6 0 0 1 2 7 6 -1 0 0 1 1234567 7654321
Sample Output 1
kerkerknight rules kerkerknight rules kerbowen rules kerbowen rules kerkerknight rules kerkerknight rules kerkerknight rules kerkerknight rules kerkerknight rules kerkerknight rules kerkerknight rules kerkerknight rules kerkerknight rules
Hints
Problem Source
Migrated from old NTUJ.
Kelvin
Subtasks
| No. | Testdata Range | Score |
|---|