PROBLEM LINK:Author: Kamil Debowski DIFFICULTY:cakewalk PREREQUISITES:none, knowledge of for or while loops in any programming language PROBLEM:Limak and Bob are friends who play a game involving eating candies. They take turns alternately with Limak starting first. Initially Limak eats 1 candy, then Bob eats 2 candies, then Limak 3 followed by Bob eating 4 candies and so on. Limak can eat at most $A$ candies, whereas Bob can eat at most $B$ candies. The person who is not able to eat the required candies in his turn will lose the game. Find out the winner of the game. Problem constraints mention that $A$ and $B$ can be at max 1000. The idea of the solution is to implement the turns of the game. We iterate over the number of candies being eaten in the current starting from 1 onwards and check whether the current player can eat the desired amount of candies or not. We can find the current player by checking the parity of number of candies in the turn being eaten. You can see that Limak always eats odd number of candies, while Bob even number of candies. If the current player is not able to eat the required amount of candies, he will lose. Pseudo code follows.
Notice that the while loop can have at most $A + B$ iterations, i.e. at most $2000$ iterations. There are 1000 test cases. So, total number of operations will be around 2000 * 1000 = 2 * 10^6 which is sufficient to pass under a sec. For a rough guideline, you can assume that around $10^8$ operations take a second to execute. Please note that this is a rough guideline, actual number of operations depend very much on the implementation of the solution and also on the architecture of the machine on which your code is being judged. You should also account for the extra constant factor due to your implementation. In fact, if you analyze carefully, you can prove that number of iterations of the while loop will much less than 2000, they will be around $\sqrt{2000}$, around 45. This is because we are subtracting $c$ candies each time, $c$ going from 1 to 2 to 3 and so on. As we know that sum of $1 + 2 + \dots + n = \frac{n \cdot (n+1)}{2} = \mathcal{O}(n^2)$. Therefore, $c$ will become greater than $A$ or $B$ in around $\sqrt{A + B}$ operations. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 Apr '17, 20:27

include<stdio.h>void main() { int n,a,b,limak,bob,i=1,flag; scanf("%d",&n); while(n) {
} where did I go wrong sir? answered 24 Apr '17, 11:47

I took a bit different approach, let's assume both Limak and Bob can eat candies till N times. Now, total candies eaten by Limak in N turns is N^2 and by Bob is N(N+1), given that former eats only odd number of candies and latter only even number of candies. We have been provided constraints for both N^2 and N(N+1) in the form of max number of candies each participant can eat. Now, we find N for each of them in each test case by equating N2 to max candies Limak can eat and N(N+1) to max candies Bob can eat. We obtain N as floor value of the above solutions, since a turn can't be partially executed. Either all candies in that turn will be eaten or the person will lose. Now for each test case, person with higher N, essentially person who can eat for more number of turns wins. In case of equal Ns, Bob wins as he plays second and Limak can't eat anymore. This yields an O(1) solution for each test case. I don't have code availabe as of now. Can share if needed later on. answered 24 Apr '17, 12:53

I have used an approach in which I have calculated the number of maximum turns a player can eat candies. There are two formulas to calculate maximum no. of turns for both players can eat candies. For 'Limak' : sqrt(total candies can eat by Limak) For 'Bob' : (sqrt(4 * total candies can eat by Bob + 1)  1)/2 Which player have maximum no. of turns will be the winner of the game. Note : These formulae can be derived using formula of summation of Arithmetic Progression (AP). Where, a = 1 (for Liamk) and 2 (for Bob) d = 2 (for both) You can check out the solution here. answered 24 Apr '17, 18:08

You may check my code here..but it is written in Java https://www.codechef.com/viewsolution/13377461 answered 24 Apr '17, 21:51

HI Sauvik, its "Limak" not "limak" and similarly its "Bob" not "bob". answered 24 Apr '17, 12:14

I have corrected your code here: https://www.codechef.com/viewsolution/13384169 What mistake you did? Initialize i=1 outside the while loop and wrote limak instead of Limak and same for Bob. Hope it helps. :) answered 24 Apr '17, 17:37

I used AP to solve it in constant time ;) First case no. of turns N1=sqrt(A) Second case N2=(1+sqrt(4B+1))/2 and (1sqrt(4B+1))/2 (whichever is positive) then if N2>=N1 then Bob will win otherwise Limak will win Note: 1. >= is used because even in the case when N2==N1 Bob will win as Limak will get the next chance in which he can't eat candy 2. Instead of storing and comparing only positives i stored and compared both values of N2 answered 24 Apr '17, 20:37

answered 15 Sep '17, 21:14

answered 14 Jun, 15:39
