Yet Another Number Game

All submissions for this problem are available.
Alice and Bob play the following game. They choose a number N to play with. The rules are as follows :
1) Alice plays first, and the two players alternate.
2) In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N.
3) The person who cannot make a move in his/her turn loses the game.
Assuming both play optimally, who wins the game ?
Input :
The first line contains the number of test cases T. Each of the next T lines contains an integer N.
Output :
Output T lines, one for each test case, containing "ALICE" if Alice wins the game, or "BOB" otherwise.
Sample Input : 2 1 2
Sample Output : BOB ALICE
Constraints : 1 <= T <= 10000 1 <= N <= 1000000000
Note : For the first test case, Alice cannot make any move and hence Bob wins the game. For the second test case, Alice subtracts 1 from N. Now, Bob cannot make a move and loses the game.
Author:  syco 
Editorial  http://discuss.codechef.com/problems/NUMGAME 
Tags  easymedium game numbertheory syco 
Date Added:  11042010 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
hey m using a turbo c++ 4.5
hey m using a turbo c++ 4.5 compiler...
i submitted d solution but its givin an error...
i can execute d prog on my pc...
can u help me out here....
http://www.codechef.com/wiki/
http://www.codechef.com/wiki/faq
k thaks got it..
k thaks got it..
Does timelimit error mean my
Does timelimit error mean my solution has errors? or is it just took long time to provide all the right answers to the test cases?
Is it possible to provide additional test cases to validate my result?
See the FAQ.
See the FAQ.
what is the meaning of "play
what is the meaning of "play optimally"?
It means each player will
It means each player will make the best possible moves, knowing their opponents will make the best possible moves too.
k got it "optimally".
MY submission time is 0.00 i
got it.... damn good way to
got it....
damn good way to present the problem......
here only when input is 1
here only when input is 1 ....alice will win else bob will win(always).....i did yhe same thing....why am i getting the wrong answer error?
please help me...........
sorry on input==2....alice
sorry on input==2....alice will win else bob will win.....my mistake in my last comment.........help me.......
If the input is 6, Alice can
If the input is 6, Alice can win by subtracting 3. Bob will be forced to subtract 1, and Alice will subtract 1 again to win.
Please verify if this is
Please verify if this is really a level 2 problem or not...because the solution is pretty straight forward and can be proved using induction.
Here is a question for test
Here is a question for test case N=1. The problem description clearly states that "In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N". So when N = 1 how can Alice subtract 1 from 1 (1 equal to N)?....as well for N=2 test case if Alice starts then 21 = 1 left for Bob to subtract from which he cannot make a move since 1 equals the new N?.....Please clarify me if Iam wrong. Thanks
Alice never subtracts 1 from
Alice never subtracts 1 from 1. The first test case is N=1; Alice cannot move therefore Bob wins. The second test case is N=2; Alice subtracts 1 and now Bob cannot move, so Alice wins.
My bad dude...I mistook the
My bad dude...I mistook the first input 2 to be N....where it is just the no of inputs....sorry about that..Thanks.
To admin: First I was getting
To admin:
First I was getting TLE error. Then I looked back into the algorithm and wrote something different. Now I am stuck with Runtim Error. Don't know where is the problem. Please help.
http://www.codechef.com/viewsolution/409212
500000005 chars is far too
500000005 chars is far too much memory to store on the stack (ie inside a function); but even if you moved it onto the heap (global) it is still too much memory.
@Stephen: Agreed! I think
@Stephen: Agreed! I think this solution should work good but why TLE? http://www.codechef.com/viewsolution/409182
Time complexity is of the order O(n^2). Is there any other algorithm with improved complexity?
Have you tried testing your
Have you tried testing your code at all? It runs forever on nearly every single input. Even if it were O(N^2), your program should be able to solve a total of 10000 test cases of size 1000000000  you wouldn't be able to solve 1 test case of size 100000 in one second with O(N^2), let alone that.
@Stephen: Damn!! I again
@Stephen: Damn!! I again din't read the problem statement carefully! :( :(. Sorry! Whole Code was wrong!
I learnt one thing here I used to think, time limit is for every individual test case, but as u say its for the entire test suit. Thanks! :)
On my machine, my program
On my machine, my program shows me total time consumed as 20 ms for 10000 inputs with each input being a random number between 1 to 1000000000... After submission, the time is .54 sec.. this is a huge difference? The language is C#..
plz look at my code.
plz look at my code.
awesome game theory problem
awesome game theory problem :
an odd # is divisible by odd only so a person getting odd number gives opponent even who in turn if gives opponent again odd(by substracting 1 which he always can as he gets even); ultimately the 1 st person always gets odd and reaches 1 at last and loses implying...
person getting odd loses so if Alice gets odd ; Bob should always try to keep him odd by taking 1 otherwise his opponent can take 1 or win himself...............here comes the meaning of optimal.
@Stephen=i am getting time
@Stephen=i am getting time limit extended again and again ...plz help me
http://www.codechef.com/viewsolution/461254
here my code ...tell me the prob ...
i am stuck with run time
i am stuck with run time error..please tell me where is the problem.....
My code is giving correct
My code is giving correct output,but at the time of submission it shows Wrong Answer.
Please Admin help me to out of my problen..
http://www.codechef.com/submit/complete/4908363084d6ea54e9b5ac
veryyyyyyyyyyyyy easy...
veryyyyyyyyyyyyy easy... loved ths one.. took only 5 minutes of deep thinking.
waw...what an problem.... i
waw...what an problem....
i coded this very complex and observed on test cases and hahaha it's so simple.
im observing it too, and get
im observing it too, and get the answer, but i still dont really know, why? :)
My program is just working
My program is just working fine in TURBOC, but i m getting TLE here, can any 1 help me.....
Following is the mine soln:
#include<stdio.h>
int main()
{
int i,t,n,flag;
scanf("%d",&t);
while(t)
{
flag=0;
scanf("%d",&n);
for(i=n/2;i>=1;)
{
if(n%i==0)
{
n=i;
i=n/2;
flag=!flag;
}
else
i;
}
if(flag)
printf("ALICEn");
else
printf("BOBn");
}
return 0;
}
#include<stdio.h>int
#include<stdio.h>
int main(){
int t,n,j,i,flag=0;
scanf("%d", &t);
if((t>=1) && (t<=10000))
{
for(i=0; i<t; i++)
{
scanf("%d", &n);
if((n<=1000000000) && (n>=1)){
for(j=n/2;n!=1;)
{
if(n%j==0)
{
n=nj;flag=!flag;j=n/2;
}
else
j;
}
if(flag)
{
printf("Alicen");
}
if(!flag)
{
printf("Bobn");
}flag=0;
}
}
}
return 0;
}
my program execute and work
my program execute and work fine in my comp. but gives wrong answer there why it is happend.......?
How do you know it works fine
How do you know it works fine on your computer.?
problem in this line if(n%2
problem in this line if(n%2 == 0) .
Hi Admin, I have submitted
Hi Admin,
I have submitted the solution with ID 532563. I have checked for some test cases and my code is working fine. But is showing WA in your system. Can you tell me for which test case it is failing or what is the reason it is showing wrong answer
Hi, Can someone take a look
Hi,
Can someone take a look at my code and see which part could be optmized ... I am getting a TLE message.
Thanks
Link to my
Link to my code:
http://www.codechef.com/viewsolution/537982
@Aparna Nobody can see your
@Aparna Nobody can see your link...the solutions to this problem are not public
@vikram  anyone who has
@vikram  anyone who has solved the problem can see code.
@Aparna  other than the fact that your algorithm is wrong (for example, you assume each player will always subtract the biggest possible factor, which certainly isn't the best strategy), N can be up to 1000000000  that's a pretty huge number. If N were a prime just under that, you'd have to loop from 1 up to 31000 or so just to find a single move, let alone the entire game or 10000 test cases of that size.
I'm afraid you'll need to start from scratch  make sure your algorithm will run in time before you write any code at all.
hey... i maked the game
hey...
i maked the game programme... but i do not understand that how can take the timer in turbo C++....???
can any one help me...??
Hi stiphen , why my code is
Hi stiphen , why my code is giving runtime error ? Is it out of memory issue ? Please let me know ...
@Admin, can you please see my
simply check if n is odd or
i use dev c++ 4.9.9.2 and my
I am getting Runtime Error. I
@gnuger :: You dont need to
aint this prob just abt odd
a very nice problem....hats
a very nice problem....hats
m getting Time Exceeded
Wow! But can sm1 explain why
I was able to finish it but I
@admin i struggle in many
@admin ....i checkd lots of
this is simple problem.. in
@vishalb1204: ALICE or BOB
@malaykeshav : H(n) : "Vk in
Consider a number N = 8 1st
import
http://www.codechef.com/views
can i use function calls
can anyone give me some more
my code #include #include
The most easiest problem on
@ admin, I am having TLE
The logic behind this is that
somebody please tell me who
coolest problem
For N=4, Bob is the winner.
In case of N=4, Shouldn't
really awsum problem....
@Admin My problem solution is
Hi All, I am able to solve
@imithya: You are correct,
#include int main() { long
huh guys this is very simple
@admin For n=7 7A6B3A2B1
@super_geek: Your assessment
awesumest problem evr...
please throw some more light
No, matter how the game is
Will it be called an optimal
Nice one... really enjoyed
what is the meaning of
Clever Problem :)
simple super problem
Very very nice problem :)
shortest code i ever made on
one line logic....
For all those who are still
Can someone please tell me if
@amitkotha1989 for n=12
Does Optimally means to
Could you please give a
What is the even  odd
remember that every player
hahahaha...i can't stop
@admin Try to put some clear
"OPTIMALLY" :P
I'm first in python in
reply to post number splrs
If a player has an odd
Lol!! The easiest problem
It was easy to solve but, can
@Admin I have submitted the
"""""!!!!!!!optimally!!!!!!!"
somebody plz check my code.it
How will you describe an
play optimally ie. at every
i.e they subtract 1 every
Lol, i am so ashamed of
if you cannot divide with
Both wants to have an even
there is no better way to put
lets say the no. is 6
Just a little bit of
The solution to this question
And these factors are taken
lol got it now...optimal
what language is TEXT,
there is one guy who just
@Admin: please take a look at
good problem!!!
can anyone explain for input
can anyone explain me for
thanks fayaz 786 for
Awesome Question !!!! I
Haha, I was writing all this
great problem ... i like the
C solution takes 2.2 MB space
pls explain me for input 4
Guy who wrote code in which
@admin plz check my
Wow, did anyone else
http://hackfbaccountlive.com/
@aakshay_777 see the limits
anarmon you dont think your
please answer me fast how it
what is wrong?? #include int
very nice and clever
MOST EASY ONE BUT LITTLE BIT
shuubham4_iitg you are
for n=15, how BOB can win?
ok working
#include int main() { int
whats the problem in my
Really cool one. Simple code,
what about 5 admin.....alice
can anyone plz help me with
if N is 10 then i think both
question is not clear..each
question is ambigous .for any
i hope that admin can look
is this an example of dynamic
easiest!!don't
i dont know about the way
Guys .. look for the O(1)
straight forward question
worst question ever solved ,
Nice way of presenting the
waw! looks like too complex
what does optimally mean