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

### Like this:

Like Loading...

*Related*

thank u for ur code.^^

but I have a question.

how did u get that algorithm??

can u explain to me?

I’m expecting ur answer.

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

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.

Thx ^^

Frankly, I extract a mathematical formula from this problem like you.

using pow.

but I got a WA repeatedly.

I think I made some mistake before

Now i got a AC.

thx again.

ps. Can you tell me ur facebook account or twitter?

my facebook acc = http://www.facebook.com/gam860720

my facebook id: http://www.facebook.com/tausiq19