Number Game RevisitedProblem code: NUMGAME2 |
All submissions for this problem are available.
Alice and Bob play the following game.They choose a number N to play with.The runs are as follows :
1.Bob plays first and the two players alternate.
2.In his/her turn ,a player can subtract from N any prime number(including 1) less than 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 format:
The first line contains the number of test cases T.Each of the next lines contains an integer N.
Output format:
Output T lines one for each test case,containing "ALICE" if Alice wins the game ,or "BOB" if Bob wins the game.
Example
Sample Input: 2 1 2
Sample Output: ALICE BOB
Constraints: 1 <= T <= 1000000 1 <= N <= 1000000000
Note : For the first test case, Bob cannot make any move and hence Alice wins the game. For the second test case, Bob subtracts 1 from N. Now, Alice cannot make a move and loses the game.
| Date: | 2010-11-23 |
| Time limit: | 1s |
| Source limit: | 50000 |
| Languages: | TCL PERL6 CLOJ GO PYTH 3.1.2 F# C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK TEXT JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
nice way to make FOOL :)
nice way to make FOOL :)
what OPTIMALLY actually means
what OPTIMALLY actually means here...
please explain using N=15??
Optimally here (and
Optimally here (and everywhere) means that both Alice and Bob will try their best to win the game. For e.g., if N=4, Bob can subtract 1, 2 or 3 but he will subtract 3 because that leads to his victory. You can try with N=15 yourself.
I assume this is not a april
I assume this is not a april fool joke.(Since this is a reputed site and they care for our time.)
I think this question is way too easier compared to any question that had apeared in any of the past contests( althoug I have not see all of them).
It would have been better if you would have given Fibonacci number instead of prime number.
(that subtraction of fibonacci numbers < N )
Thanks.
Happy fools day, the odd one
Happy fools day, the odd one out the lot.
Happy fools day. Nice one!!
Happy fools day. Nice one!!
if BOB makes the first move
if BOB makes the first move in first test case and substracts 1. Then the remaining no is 0. So alice cant make a move and so BOB should win . So why does the output answer says ALICE. Care to Explain plz ....
@Karanveer In the problem
@Karanveer In the problem statement, it has been mentioned that "In his/her turn, a player can subtract from N any prime number (including 1) less than N."
Bob cannot subtract 1 in his turn because it is not less than N (which is 1).
k. Thanks shyam . Didnt
k. Thanks shyam . Didnt notice that.
My logic is correct. I am
My logic is correct. I am getting right answer for test cases and a few more. My submission however gives TLE. Care to explain anyone?
@BharathYour program did not
@Bharath
Your program did not finish executing within the specified time limit for this problem. So you get 'Time Limit Exceeded', irrespective of the correctness of your logic.
PLEASE ANY one explain
PLEASE ANY one explain me
what is mean by OPTIMALLY?
explain for N=5 || n=7;
@piyush Optimally in the
@piyush Optimally in the
Guys i m a noob out here n i
Guys i m a noob out here n i m unable to get through the question:
Is it askign for the following?
Let a random number has been choosen Say 22
Bob : 19 //New Num : 3
Alice : 2 // New Num : 1
Bob cannot subtract anymore so ALICE is winner...
May i correct
Ronak, This is not optimal.
Ronak, This is not optimal. If Bob choose 19, Alice can choose 1. Then Bob has to choose 1 and Alice will Win. Thus 19 by Bob is not the optimal move.
@RONK AGRAWAL:
@RONK AGRAWAL: BOB:17(5)
ALICE:3(2)
BOB:1
So BOB is the winner !
can any body tell me what may
can any body tell me what may be the reason for TLE IN MY submission
please
@Note : For the first test
@Note : For the first test case, Bob cannot make any move and hence Alice wins the game. For the second test case, Bob subtracts 1 from N. Now, Alice cannot make a move and loses the game.
i think in the second case BOB loses by substracting 1 and alice still wins(she can substract 1 now).
sorry!^ my bad
sorry!^ my bad
if we think
if we think optimally...always bobs wins...never alice once except the no is 1.
how i can get ride of time
how i can get ride of time limit execexed
what the wrong answer for
what the wrong answer for what value
i have more or less figured
can some plz give some test
can some plz give some test inputs along with itz resultz :)
Hey, can we download ur