A Game of Thrones
All submissions for this problem are available.
Bran and Tyrion are the last two high lords fighting for the Iron Throne. With a mutual agreement that included all knights of the realm, it was decided to settle the issue with a game of thrones, of course not a game of swords but a game of numbers, after all one of them is a cripple and other is a dwarf. Seven wisest men of the realm came forward and forged rules of this game which are as follows :
- Initially N numbers were written down on a notebook (possibly with multiple copies of every number).
- Players alternate their turns with Bran playing first.
- In the first turn Bran gets to choose a number of his choice from the numbers written on the notebook and declare it as the current number of the game.
- After that in every move this is what they do : let's say the current number of the game is u. They erase u from the notebook (if u was written multiple times, they erase it only once) and declare one of the numbers still written on the notebook v as current number of the game. v can be chosen iff prime factorization of u and v differ by exactly 1 prime factor. ( Read notes for a more formal definition)
- The player who can't make a move loses the game.
You're one of Varys' spider and he has asked you to predict the outcome of this game beforehand so that he can devise future strategy. So you've to find out who has a winning strategy assuming both players play optimally.
1) v can be chosen after u iff either of the following conditions hold :
- v > u and u | v and (v / u) is prime
- u > v and v | u and (u / v) is prime
2) A natural number if prime if it has exactly two distinct positive factors. 1 is not a prime number.
First line of the input contains a single integer N denoting number of
different numbers written in the notebook. Then follow N lines. Each of
the following lines contain two space separated integers : ui
and ci where ui
is the ith distinct integer written on notebook and it has been repeated ci
number of times.
Your program should print Bran if he has a a winning strategy else it should print Tyrion. Also in case Bran could win, your program must output the smallest number Bran could choose in the first turn to ensure a win. See sample output for details.
Input: 3 2 3 14 3 21 2 Output: Bran 21
1 <= N <= 500
1 <= ui
1 <= ci
|Tags||aug12, flow, hard, matching, yellow_agony|
|Time Limit:||0.1 - 0.190817 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.