### PROBLEM LINK:

**Author:** Kamil Debowski

**Primary Tester:** Marek Sokołowski

**Secondary Tester:** Praveen Dhinwa

**Editorialist:** Praveen Dhinwa

### 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.

```
limakCandies = 0 // denotes number of candies eaten by Limak.
bobCandies = 0 // denotes number of candies eaten by Bob.
c = 1;
while (true)
// In this turn the person should eat exactly c candies.
// if c is odd, then it is Limak's turn, otherwise Bob's.
if c % 2 == 1:
limakCandies += c;
if (limakCandies > A):
// limak can't eat these c candies, so Bob will win.
winner = "Bob";
break;
else:
bobCandies += c;
if (bobCandies > B):
// Bob can't eat these c candies, so Limak will win.
winner = "Limak";
break;
c += 1;
```

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.