Hide

Problem B
Cuboid Slicing Game

/problems/cuboidslicinggame/file/statement/en/img-0001.png

Ruben and Albert are what you can call abnormally smart. They are also both very fond of mathematically inspired games. Their only problem is that most games are too easy for them, and they end up beating everyone who dares challenge them. Because of that, they’re now mostly playing against each other. To make things interesting, they had a professor design a new game for them.

This new game was interesting at first. Nowadays, however, Albert often complains that it is impossible for him to win a particular round. After long discussions, they’ve now decided to take this a step further, and actually figure out who’d win if they both played optimally. They need you to write a computer program that does this for them.

A state in the game consists of one or more $x\times y\times z$ cuboids. A (legal) move is choosing a cuboid, then a value for each of the three axes (basically choosing three planes), and then cutting the cuboid along these (thus removing a $1\times y\times z$, $x\times 1\times z$ and a $x\times y\times 1$, all overlapping, cuboid). In effect you’ve created between $0$ and $8$ (inclusive) smaller cuboids. All three planes cut from the cuboid need to be on the cuboid (you can’t cut away a hypothetical cuboid on the outside of the real one).

An example might be in order. You’ve chosen a $3\times 5\times 4$ cuboid, and are about to cut it. You now need to choose the three planes. This means you need an $x$ between $1$ and $3$, a $y$ between $1$ and $5$ and a $z$ between $1$ and $4$. Say you choose $2$, $1$ and $3$, respectively. The first cut would alone cut the cuboid into two $1\times 5\times 4$ cuboids, the second into a single $3\times 4\times 4$ cuboid, while the third would alone cut the cuboid into a $3\times 5\times 1$ and a $3\times 5\times 2$ cuboid. Put together these cuts produces $4$ new smaller cuboids, of sizes $1\times 4\times 1$,$1\times 4\times 1$,$1\times 4\times 2$ and $1\times 4\times 2$. Note that cutting a cuboid with an axis of size $1$ would remove it altogether.

The players take turns making a move. The winner is the player that removes the last cuboid.

Input

The first line of input is a line containing either RUBEN or ALBERT, the name of the player who starts that particular round.
Then follows a line containing $N$, the number of cuboids that particular game starts with.
$N$ lines follow, each describing a cuboid. A cuboid description consists of three numbers, $x$, $y$ and $z$, the size of that particular cuboid.

Output

Output the name of the player that wins the game (either RUBEN or ALBERT).

Limits

  • $1 \le N \le 100$

  • $1 \le x,y,z \le 30$

Sample Input 1 Sample Output 1
RUBEN
1
4 1 7
RUBEN
Sample Input 2 Sample Output 2
ALBERT
2
4 4 4
2 2 2
RUBEN
Sample Input 3 Sample Output 3
ALBERT
3
6 3 7
18 1 9
7 5 8
ALBERT

Please log in to submit a solution to this problem

Log in