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