// http://www.codechef.com/problems/NUMGAME/
// Runtime : 0.01s
// Memory : 2.5M
// Tag : Gotcha
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;
int main ()
{
int testCase;
scanf ("%d", &testCase);
while ( testCase-- ) {
int n;
scanf ("%d", &n);
if ( n % 2 ) printf ("BOB\n");
else printf ("ALICE\n");
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

Could u please explain why this solution is going to work.. I tried my math but was unable to do so !

@sukhmeet,

remeber both player plays optimally, so u have to think irregardless

if a player anyhow get 1, he will loose

so, 1 = loosing state

if a player anyhow get 2, he will win

because, he can easily subtract 1 from 2, [1 is a prover divisor of 2 and 1 < 2]

if he does so, he will return 1 to his opponent

and we know, 1 = loosing state

so 2 = wining state

if a player anyhow get 3, he will loose

because, he has only one way, 3 – 1 = 2

he will return 2 to his opponent

and we know, 2 = wining state

so 3 = loosing state

if a player anyhow get 4,

he has two different ways,

4 – 1 = 3

4 – 2 = 2

as he plays optimally, he will choose the 1st one, 4 – 1 = 3

he will give 3 to his opponent

and we know, 3 = loosing state

so 4 = wining state

if a player anyhow get 5, he will loose

because, he has only one way, 5 – 1 = 4

he will return 4 to his opponent

and we know, 4 = wining state

so 5 = loosing state

if a player anyhow get 6,

he has three different ways,

6 – 1 = 5

6 – 2 = 4

6 – 3 = 3

as he plays optimally, he will choose the 1st / 3rd one

thus he can give his opponent a loosing state

and from a loosing state, no one can escape but loose the game

he can also choose 6 – 2 = 4, where 4 = wining state

but as he plays optimally, he never gonna do that

so 6 = wining state

and so on …

try to solve some more in this way

i hope it will help to go in right direction

Nice Explanation 🙂

perfect….!

great !

pls explain why player cannot remove 2 when n=4. i mean what do we actually mean by “playing optimally”?