101 Hack 44 - Alice and Bob's Silly Game

Alice and Bob invented the following silly game:

• The game starts with an integer, , that's used to build a  of  distinct integers in the inclusive range from to  (i.e., ).
• Alice always plays first, and the two players move in alternating turns.
• During each move, the current player chooses a prime number, , from . The player then removes  and all of its multiples from .
• The first player to be unable to make a move loses the game.

Alice and Bob play  games. Given the value of  for each game, print the name of the game's winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Note: Each player always plays optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.

Input Format

The first line contains an integer, , denoting the number of games Alice and Bob play. 
Each line  of the  subsequent lines contains a single integer, , describing a game.

Constraints

Subtasks

•  for  of the maximum score

Output Format

For each game, print the name of the winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Sample Input 0

3
1
2
5

Sample Output 0

Bob
Alice
Alice

Explanation 0

Alice and Bob play the following  games:

1. We are given , so . Because Alice has no valid moves (there are no prime numbers in the set), she loses the game. Thus, we print Bob on a new line.
2. We are given , so . Alice chooses the prime number  and deletes it from the set, which becomes . Because Bob has no valid moves (there are no prime numbers in the set), he loses the game. Thus, we print Alice on a new line.
3. We are given , so . Alice chooses the prime number  and deletes the numbers and  from the set, which becomes . Now there are two primes left,  and . Bob can remove either prime from the set, and then Alice can remove the remaining prime. Because Bob is left without a final move, Alice will always win. Thus, we print Alice on a new line.

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos( 0.0 );
8.  
9. inline int _Int(){ int x; scanf( "%d", &x ); return x; }
10. inline LL _LLi(){ LL x; scanf( "%lld", &x ); return x; }
11. void pruts(){ puts( "-1" ); exit( EXIT_SUCCESS ); }
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. int prime[ S ];
31. int freq[ S ];
32.  
33. void seive(){
34.     int sq = sqrt(S);
35.     for( int i = 2; i <= sq; i++ ){
36.         if( !prime[ i ] ){
37.             for( int j = i+i; j <= S; j += i )prime[ j ] = 1;
38.         }
39.     }
40.     for( int i = 2; i < S; i++ ){
41.         if( !prime[ i ] )freq[ i ]++;
42.         freq[ i ] += freq[ i-1 ];
43.     }
44.  
45. }
46.  
47. void Love(){
48.     seive();
49.     int g = _Int();
50.     while( g-- ){
51.         int n = _Int();
52.         puts( ( freq[ n ]&1 )? "Alice" : "Bob" );
53.     }
54. }
55.  
56. int main(){
57.     #ifndef ONLINE_JUDGE
58. //        freopen("in.txt", "r", stdin);
59. //        freopen("n.txt", "w", stdout);
60.     #endif
61.     Love();
62.     return 0;
63. }