The solution can be found by observation that if one player finds the total number of ball that is equal (2^n -1) then the player is looser.

i.e. we find for n=3 it is true,

so, if n=3 1st player looses,

for n=4 1st player wins

*n=5 1st player wins, for n=6 1st player wins, for n=7 1st player looses, why cause for n=7 balls can be divided into pairs following rules as follows: (6,1),(5,2),(4,3), so there is no way to give an opponent player a loosing number of balls. Same for 15,31 and so on. for 15 pairs are:(14,1),(13,2),(12,3),(11,4),(10,5),(9,5),(8,7), so 1st player is giving the winning case satisfying number of balls. *

*And why 14,13,12…..8 are winning case satisfying cause each can be paired as (7,7),(7,6)(7,5)…(7,1) allowing the 2nd player to provide the 1st player loosing case satisfying number of balls.*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <cstdio> using namespace std; int main() { int n; while(scanf("%d",&n),n!=0) { if(n%2==0) cout<<"Alice\n"; else { n+=1; while(n>1) { if(n%2) break; n/=2; } if(n!=1) cout<<"Alice\n"; else cout<<"Bob\n"; } } return 0; } |