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.

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).I don't know proof but solution look like this series. If a(n) = 1, then first player win, otherwise second player win.

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 thesumof`2k - 1`

-th turn and`2k`

-th turn to be $$$2 k$$$ or $$$2 k + 1$$$. so we may write $$$n$$$ as: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:

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 thesumof`2k- 2`

-th turn and`2k - 1`

-th turn to be $$$2 k - 1$$$ or $$$2 k$$$, we can write $$$n$$$ as: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: