All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Two players are playing a game. The game is played on a sequence of positive integer pairs. The players make their moves alternatively. During his move the player chooses a pair and decreases the larger integer in the pair by a positive multiple of the smaller integer in the pair in such a way that both integers in the pair remain positive. If two numbers in some pair become equal then the pair is removed from the sequence. The player who can not make any move loses (or in another words the player who encounters an empty sequence loses). Given the sequence of positive integer pairs determine whether the first player can win or not (assuming that both players are playing optimally).
InputThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test starts with an integer N denoting the number of pairs. Each of the next N lines contains a pair of positive integers.
OutputFor each test case, output a single line containing "YES" if the first player can win and "NO" otherwise.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100
- All other integers are between 1 to 108
- The integers in each pair will be different
Input: 3 1 2 3 2 4 5 5 6 2 2 3 3 5 Output: NO NO YES
Example case 1. The first player don't have any choice other subtracting 2 from 3. So during the turn of the second player integer pair will be (2,1). The second player will win by subtracting 1 from 2.
Example case 2. If the first player choose to move (4,5) to (4,1) the second player will make it to (1,1). If the first player choose to move (5,6) to (5,1) the second player will make it to (1,1). So regardless of the move of the first player, the second will always win.
Example case 3. The first player will select pair (3,5) and make it to (3,2). Now both pairs are equal. So whatever the move of second player he will just mirror that move in another pair. This will ensure his win.
|Tags||cook42, easy, game-theory, satej , sprague-grundy|
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.