CodeChef : Yet Another Number Game (NUMGAME)



// 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

6 thoughts on “CodeChef : Yet Another Number Game (NUMGAME)

  1. @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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s