### Блог пользователя myHandle

Автор myHandle, история, 12 месяцев назад, ,

Hello,

Can someone explain the logic [and formal proof why this logic works] to solve this problem?

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.

•
• -3
•

»
12 месяцев назад, # |
-21

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

}

•  » » 12 месяцев назад, # ^ |   0 I asked the logic and not the solution.
•  » » » 12 месяцев назад, # ^ |   -33 Go find the logic from my code then
•  » » » » 12 месяцев назад, # ^ |   0 Actually, I have seen the solutions after the round but I need a formal proof of the logic used. Thanks.
•  » » » » 12 месяцев назад, # ^ |   0 I think this code is simple and better than yours. #include using namespace std; int main() { int n,a,k;scanf("%d",&n); for(int i=0; i<500; i++) { if(n==1) {printf("1\n"); return 0;} k = 0; while( n % (1<
 » 12 месяцев назад, # |   0 Auto comment: topic has been updated by remidinishanth (previous revision, new revision, compare).
 » 12 месяцев назад, # |   +1 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'.
•  » » 12 месяцев назад, # ^ |   0 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.
 » 12 месяцев назад, # |   0 I came up with this, it passes, but is it really correct? It just mirrors the interactor output after the first number.  int N; cin >> N; int num = 1; for (int i = 1; i <= N - 1; ++i) { if (N % i == 0 && (N / i) % 2 == 1) { num = i; break; } } for (int i = 0; i < 500; ++i) { cout << num << "\n"; cout.flush(); cin >> num; }