// CCC 2008, Senior Contest, Problem 5: Nukit
#include <iostream>
#include <fstream>
using namespace std;
// the 5 reactions that can be applied
int rc[5][4] = { {2, 1, 0, 2}, {1, 1, 1, 1}, {0, 0, 2, 1}, {0, 3, 0, 0}, {1, 0, 0, 1} };
// memoization tables. Requires about 230 kilobytes of memory
bool hasCalculated[31][31][31][31];
bool memoizedValue[31][31][31][31];
// Applies reaction to state. If the given reaction cannot be applied, it returns false.
// It passes the array state by reference, and modifies its values.
bool react(int (&state)[4], int reaction)
{
for (int i = 0; i < 4; ++i)
{
if (state[i] < rc[reaction][i])
return false;
state[i] -= rc[reaction][i];
}
return true;
}
// main recursive function that determines if state is a winning or losing state.
// It returns true if state is a winning state or false if state is losing a losing state.
bool isWinning(int state[4])
{
// memoization: if the given state has already been calculated, simply
// return the memoized value
if (hasCalculated[state[0]][state[1]][state[2]][state[3]] == true)
return memoizedValue[state[0]][state[1]][state[2]][state[3]];
// otherwise, calculate it:
int next[4];
for (int i = 0; i < 5; ++i)
{
// assign next to state
for (int j = 0; j < 4; ++j)
next[j] = state[j];
// this is a winning state: there exists a losing state that can be reached
// from this state. Note that in C++ the first condition must be true in
// order for the second condition to be executed when using logical AND.
// Thus isWinning is terminable.
if (react(next, i) == true && isWinning(next) == false)
{
hasCalculated[state[0]][state[1]][state[2]][state[3]] = true;
memoizedValue[state[0]][state[1]][state[2]][state[3]] = true;
return true;
}
}
// this is a losing state: either all states that can be reached from this
// state are winning states or no reactions can be applied to this state
hasCalculated[state[0]][state[1]][state[2]][state[3]] = true;
memoizedValue[state[0]][state[1]][state[2]][state[3]] = false;
return false;
}
// MAIN PROGRAM EXECUTION
int main()
{
// File I/O declarations
ifstream fin ("s5.in");
int lines;
fin >> lines;
// initializes the hasCalculated array
for (int i = 0; i < 30; ++i)
for (int j = 0; j < 30; ++j)
for (int k = 0; k < 30; ++k)
for (int l = 0; l < 30; ++l)
hasCalculated[i][j][k][l] = false;
int state[4];
for (int i = 0; i < lines; ++i)
{
fin >> state[0] >> state[1] >> state[2] >> state[3];
// if state is winning, then output Patrick. Otherwise, output Roland.
cout << ((isWinning(state) == true) ? "Patrick" : "Roland") << "\n";
}
// waits for enter key
cin.get();
return 0;
}
