Hello,↵
↵
Can someone explain the logic [and formal proof why this logic works] to solve this problem?↵
↵
[https://csacademy.com/contest/round-64/task/limited-moves/](https://csacademy.com/contest/round-64/task/limited-moves/)↵
↵
Consider a heap of **N** objects. Two players take turns playing the following game:↵
↵
At his very first move, the first player removes from the heap between **1** and **N-1** objects↵
After that, at each step the player to move can remove any number of objects between 1 and the number of objects removed by the other player at the previous move↵
When the heap becomes empty, the player to move loses the game.↵
↵
[UPD.]↵
↵
I know that removing the number of objects from Last on bit works. The Last on-bit, I mean the below.↵
↵
~~~~~↵
int k=0;↵
while( n % (1<<(k+1)) == 0)↵
k++;↵
printf("%d",(1<<k));↵
fflush(stdout);↵
n -= (1<<k);↵
~~~~~↵
↵
↵
↵
I need a formal proof/Argument that why is this working. Or why this is guaranteed to work?↵
↵
Thank you.↵
↵
Can someone explain the logic [and formal proof why this logic works] to solve this problem?↵
↵
[https://csacademy.com/contest/round-64/task/limited-moves/](https://csacademy.com/contest/round-64/task/limited-moves/)↵
↵
Consider a heap of **N** objects. Two players take turns playing the following game:↵
↵
At his very first move, the first player removes from the heap between **1** and **N-1** objects↵
After that, at each step the player to move can remove any number of objects between 1 and the number of objects removed by the other player at the previous move↵
When the heap becomes empty, the player to move loses the game.↵
↵
[UPD.]↵
↵
I know that removing the number of objects from Last on bit works. The Last on-bit, I mean the below.↵
↵
~~~~~↵
int k=0;↵
while( n % (1<<(k+1)) == 0)↵
k++;↵
printf("%d",(1<<k));↵
fflush(stdout);↵
n -= (1<<k);↵
~~~~~↵
↵
↵
↵
I need a formal proof/Argument that why is this working. Or why this is guaranteed to work?↵
↵
Thank you.↵
