### a2dalek's blog

By a2dalek, history, 7 weeks ago, I can't solve this problem: There are N stones (N<=1e18) and two players. They play alterably. At the k-th turn, player must take at least 1 stone but can take no more than k stones (player at the first turn can take no more than 1, player at the second turn can take no more than 2,..). Who takes the last stone is the winner. Give N, who will win the game, player 1 or player 2 ? Please help me. Tks. Comments (13)
 » i think the winner is affected by minimum x satisfied (x-1) + x >= k that is odd or not
•  » » proof?
•  » » » if winner take X stones to win in X rounds, in previous round, loser must take one stone ( take least stones as much as possible not to lose in next round )
•  » » » But this is only my opinion. that could be wrong answer
•  » » » ah, that is wrong answer sorry
•  » » » » u have a nice face sir.
•  » » » » » subscribe "RaLo" in youtube
•  » » Sorry because my blog was unclear. I updated.
 » I think player 2 wins if n%(k+1) == 0, else player 1 wins.
•  » » Sorry because my blog was unclear. I updated.
 » Auto comment: topic has been updated by a2dalek (previous revision, new revision, compare).
 » 7 weeks ago, # | ← Rev. 2 →   I don't know proof but solution look like this series. If a(n) = 1, then first player win, otherwise second player win.
 » 7 weeks ago, # | ← Rev. 2 →   Inspired by Sakhiya07's result, I give a proof.Note that whatever in 2k - 1-th turn, first player take, the second player could make the sum of 2k - 1-th turn and 2k-th turn to be $2 k$ or $2 k + 1$. so we may write $n$ as: $n = 2 + 4 + \cdots + 2 k - 2 + m$if $m = 2k, 2k + 1$, then since at 2k - 1-th turn, the first play take at most $2 k - 1$ stones, the second player will win.Now, if $2k \leq m \leq 2k + k$, we may write $n$ as: $n = 3 + 5 + \cdots + 2l + 1 + 2l + 2 + \cdots + 2k - 2 + 2k$Similar, we know the second player will win.Thus, if $k^2 + k \leq n \leq k^2 + 2k$, the second player will win.Similar, whatever in 2k - 2-th turn, second player take, the second player could make the sum of 2k- 2-th turn and 2k - 1-th turn to be $2 k - 1$ or $2 k$, we can write $n$ as: $n = 1 + 3 + \cdots + (2k - 1) + m$easy to easy if $2k + 1 \leq m \leq 2k + 1 + k$, the first player will win.Thus, if $k ^ 2 \leq n < k^2 + k$, the first player will win.Code is easy: bool f(long long n) { long long k = std::sqrt(n + 0.1); return n < (k + 1) * k; }