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/
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.
include <bits/stdc++.h>
using namespace std;
void make(int n,int k,int moves){ for(int i=moves;i<500 && n > 0;i++){ printf("%d\n",k); fflush(stdout); if(n == 1) return; int a; scanf("%d",&a); n -= a; n-=a; n-=k; k = min(k,a); } }
int main() { int n; scanf("%d",&n); int moves= 0; int mn = 0; for(int i=0;i<500;i++){ if(n == 1){ puts("1"); fflush(stdout); return 0; } else if(n == 2){ puts("2"); fflush(stdout); return 0; } for(int j=29;j>=0;j--){
} } for(int i=29;i>=0;i--){ if(n == 1){ puts("1"); fflush(stdout); return 0; } else if(n == 2){ puts("2"); fflush(stdout); return 0; } if((1 << i) <= n){ int k = n - (1 << i); printf("%d\n",k); n-=k; fflush(stdout); scanf("%d",&k); moves++; n -=k; if(n == 0){ return 0; } make(n,k,moves); if(moves == 500) return 0; } } return 0;}
I asked the logic and not the solution.
Go find the logic from my code then
Actually, I have seen the solutions after the round but I need a formal proof of the logic used. Thanks.
I think this code is simple and better than yours.
Auto comment: topic has been updated by RNR (previous revision, new revision, compare).
If n is odd then we win by removing 1. So no one will move to odd n and the game will be always on even numbers. But now we can divide all numbers by 2 and repeat our argument. It is easy to see that this strategy is exactly 'remove last 1-bit'.
Thank you... I got it when n is odd, the strategy will be 1,1,1,1,..... it can be easily be seen. And if n we are removing the last 1-bit such that when the opponent removes some number of objects it leads to the above strategy... Cool. Thanks a lot.
I came up with this, it passes, but is it really correct? It just mirrors the interactor output after the first number.