UVa : 12293 (Box Game)



// http://uva.onlinejudge.org/external/122/12293.html
// Tag: Game
// Runtime: 0.012s

#include <stdio.h>
#define LL long long

int main ()
{
    LL n;

    while ( scanf ("%lld", &n) && n ) {
        LL num = 1;
        while ( num < n ) {
            num *= 2;
            num++;
        }

        if ( num == n ) printf ("Bob\n");
        else printf ("Alice\n");
    }

    return 0;
}

5 thoughts on “UVa : 12293 (Box Game)

  1. @Seong Joong Kim
    u r welcome 🙂

    actually its a common technique .. there r lots of problems in various online judges problem set. once u get the logic, it would pretty simple for u to code.

    for example, if n == 1 then its a loosing state
    because, irrespective of any player, whoever get 1 ball (n = 1) in front of him, is a looser.

    if n == 2, its a winning state
    because, you can take 1 ball from the box and make ur opponent to be in a loosing state. so, its a winning state for the current person.

    if n == 3, its a loosing state
    because, after taking fewer ball, u need to redistribute the 3 balls, and there is only one way
    1 + 2 = 3
    u have no other way left but to help your opponent to be in a winning state ( 1 ball in a box, and 2 balls in another box )

    if n == 4 its a winning state
    because, redistributions are as follows
    1 + 3
    2 + 2
    after taking fewer balls, u can make either one ( 1 + 3 or 2 + 2 )
    but u should definitely go for 1 + 3. because thus ur opponent will be given a loosing state

    similarly if you try with urself, u will find
    n = 5 -> winning state
    n = 6 -> winning state
    n = 7 -> loosing state
    n = 8 to 14 -> winning state
    n = 15 -> loosing state and so on

    now you can make an easy formula:
    if n == (2 to the power x) – 1 then, its a loosing state
    else its a winning state

    where, x >= 1

    as Alice moves first according to problem statement, so if n = 1, 3, 7, 15, 31, 63, 127 and so on ….. Alice will loose. otherwise, Bob will loose

    you can take a look at the following post for a similar problem .. good luck 🙂

    https://tausiq.wordpress.com/2010/11/25/codechef-yet-another-number-game-numgame/

  2. Thanks….Ur discussion is more helpful than code for building logic which make oneself programmer.
    (specially myself). It also inspire me to solve identical problem…thanks again.

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