Humpty-Dumpty and the Game
All submissions for this problem are available.
Humpty and Dumpty are very close friends. Humpty has recently performed exceptionally well in the End semester exams, so he has gained a lot of confidence. He challenges Dumpty for a Nim game. But Dumpty, as we all know, completely outwitting him, challenges him for a unique game of its own kind. Humpty settles after the argument that they will use following function somewhere in the game.
def check( x, y, k): if y> x: return 0 p = k while x>0 and y>0: if (y%k) > (x%k): return 0 x = x/p y = y/p return 1
Here % is the modulus operator.
The Game is as follows:
N positive integers are given, let them be represented by A to A[N]. Before the first turn, players decide a positive integer k (k>1). The two players take turns. Now, in each turn the player should choose one positive integer x among the given N integers, and he can reduce the integer by an amount y (y is also a positive integer) if check( x, y, k) returns TRUE. The game ends when no move can be made. And obviously the player who makes the last move wins.
Can you find who will win the game, if both players play optimally, given the N integer numbers and an integer k, considering that Humpty always takes the first move.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains space separated integer values N and k. Second line of each test case consists of N space separated integers.
Output T lines, each representing the winner. Output 1 if Humpty wins and 2 if Dumpty wins.
1 ≤ T ≤ 105
1 ≤ N ≤ 105
2 ≤ k ≤ 105
1 ≤ A[i] ≤ 1018 for 1 ≤ i ≤ N
Input: 2 3 4 5 6 9 3 3 1 5 2 Output: 1 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.