2008 Canadian Computing Competition, Stage 1

Problem S5: Nukit

Canada's top two nuclear scientists, Patrick and Roland, have just completed the construction of the world's first nuclear fission reactor. Now it is their job to sit and operate the reactor all day, every day. Naturally they got a little bored after doing this for a while and as a result, two things have happened. First, they can now control the individual reactions that happen inside the reactor. Second, to pass the time, they have invented a new game called Nukit.

At the beginning of Nukit, a number of particles are put in the reactor. The players take alternating turns, with Patrick always going first. When it is a player's turn to move, they must select some of the remaining particles to form one of the possible reactions. Then those particles are destroyed. Eventually there will be so few particles that none of the reactions can be formed; at this point, the first person who is unable to form a reaction on their turn loses.

In our universe you can assume that there are only 4 types of particles: A, B, C, D. Each reaction is a list of particles that can be destroyed on a single turn. The five reactions are:

1. AABDD
2. ABCD
3. CCD
4. BBB
5. AD

For example, the first reaction "AABDD" says that it is allowable to destroy two A, one B, and two D particles all at the same time on a turn.

It turns out that, no matter how many particles start off in the reactor, exactly one of Patrick or Roland has a perfect winning strategy. By player X has a perfect winning strategy, we mean that no matter what the other player does, player X can always win by carefully choosing reactions. For example, if the reactor starts off with one A, five B, and three D particles then Roland has the following perfect winning strategy: "if Patrick forms reaction BBB initially, then form reaction AD afterward; if Patrick forms reaction AD initially, then form reaction BBB afterward." (The strategy works because either way, on Patrick's second turn, there are not enough particles left to form any reactions.)

Given the number of each type of particle initially in the reactor, can you figure out who has a perfect winning strategy?

Input

The first line of input contains n, the number of test cases (1 ≤ n < 100). Each test case consists of 4 integers separated by spaces on a single line; they represent the initial number of A, B, C and D particles. You can assume that there are initially between 0 and 30 (inclusive) of each type of particle.

Output

Sample Input

6
0 2 0 2
1 3 1 3
1 5 0 3
3 3 3 3
8 8 6 7
8 8 8 8

Sample Output

Roland
Patrick
Roland
Roland
Roland
Patrick

Partial Explanation

The first output occurs since Patrick loses immediately, since he cannot form any reaction. (Roland's perfect winning strategy is "do nothing.")

The second output occurs since Patrick has the perfect winning strategy "form reaction ABCD," which makes Roland lose on his first turn.

The third output is explained in the problem statement.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 64M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

When I submit my code through the judge it says "Traceback most recent..." but I don't get this when I test this myself. What could it be?

When I run it separately, I get:

[code][quote]Traceback (most recent call last):
  File "prog.py", line 67, in <module>
ValueError: invalid literal for int() with base 10: '0 2 0 2'[/quote][/code]
You're trying to read one value at a time, but raw_input() gets a whole line, which obviously cannot be parsed into a single int. 

            

            

            
            

            
Traceback (most recent call last): 
  File "prog.py", line 67, in <module> 
ValueError: invalid literal for int() with base 10: '0 2 0 2'