Sort 33 Discussions, By:
Please Login in order to post a comment
This task needs better explanation, current is not understandable at all.
For the first testcase, we can see that the saint can destroy the first stone and win the game.*
this must be joke, right ?
So they don't gradually get more difficult... it's straight from Hello World! to ridiculously difficult? Nice. I'm out.
Answers for N = 6, 8, 10 could be 3, 8, 5. Isn't it? Can anyone explain the given test case?
O(1) solution, passes all test cases. I'm pretty sure this beats the editorial solution, assuming that for N <= 1 billion, we can find floor(lg N) in O(1) time (python3 has a builtin "frexp" function that does this). For arbitrary N, there's a O(lg lg N) method to obtain floor(lg N), so that would be the complexity if we allowed arbitrarily large integers.
from math import frexp
if n&1: return 1
return 1<<y-2 if (x^y)+1==y else (1<<y-1)-(1<<(x^y))+1
for _ in range(int(input())):
Explanation: first examine the nimber of every pile using the maximum excludant, e.g. smallest non-negative integer that is not equal to the nimber of any positions reachable from current position. It is easy to see that a pile of n stones has nimber L(n)=1+floor(lg n). Note also L(0)=0 by definition. The first few are
N = 0 1 2 3 4 5 6 7 8 9 10 11 12
L = 0 1 2 2 3 3 3 3 4 4 4 4 4
By the Sprague-Grundy theorem, cumulative XOR, which we denote X(N), of all nimbers tells you whether first person wins: if X(N)=0, first person loses, and otherwise first person wins. By inspection, we see that for any n>=0, X(2n+1)=1 and X(2n)=1^L(2n). This is always nonzero, so the first player can always win.
In order to win, the first player must choose some pile m and change the nimber of that pile from L(m) to X^L(m). For N odd, just choose m=1, take one stone, and that's the answer. For N even, it's trickier. The minimum stones taken corresponds (but is not equal) to the minimum positive value of L(m)-X(N)^L(m). By inspection, this can be chosen by setting L(m)=y=2**floor(lg X(N)). The minimum value of m that gives this nimber is m=2**(y-1). We need to remove the minimum number of stones from this pile of m so that the new nimber is X(N)^y. If the new nimber is one less than the old nimber, then there's only one option: remove half of m. Otherwise, we go down to the largest possible pile whose nimber is X(N)^y, which is given by 2**(X(N)^y)-1.