### 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.

• -15

 » 7 weeks ago, # |   0 i think the winner is affected by minimum x satisfied (x-1) + x >= k that is odd or not
•  » » 7 weeks ago, # ^ |   0 proof?
•  » » » 7 weeks ago, # ^ |   0 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 )
•  » » » 7 weeks ago, # ^ |   0 But this is only my opinion. that could be wrong answer
•  » » » 7 weeks ago, # ^ |   0 ah, that is wrong answer sorry
•  » » » » 7 weeks ago, # ^ |   0 u have a nice face sir.
•  » » » » » 7 weeks ago, # ^ |   0 subscribe "RaLo" in youtube
•  » » 7 weeks ago, # ^ |   0 Sorry because my blog was unclear. I updated.
 » 7 weeks ago, # |   0 I think player 2 wins if n%(k+1) == 0, else player 1 wins.
•  » » 7 weeks ago, # ^ |   0 Sorry because my blog was unclear. I updated.
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by a2dalek (previous revision, new revision, compare).
 » 7 weeks ago, # | ← Rev. 2 →   +14 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 →   +8 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; }