PROBLEM LINK:
Author: Suthirth V
Tester: Suthirth V
Editorialist: Suthirth V
DIFFICULTY:
Simple
PREREQUISITES:
Logic, Math
PROBLEM:
After Lee Sedol lost to Alpha GO AI, he meets his counterpart Garry Kasparov to find solace. What started as a calm conversation soon turns into a heated argument as they decide to challenge themselves in a game of Konkatonka.
In the most common form of Konkatonka, a transparent box is kept and filled with plastic cubes marked with numbers 1 to M where M is a natural number. The players take alternative turns until the end of the game. In each turn, a player picks a cube, marked x and also all the cubes marked with divisors of x out of the box. The game goes on till all the cubes in the box are removed. The player to pick up the last cube remaining inside the box is the winner.
Input:
First Line : a natural number t indicating the number of test cases In each line of the test case, two integers are given separated by a single space. The first integer M is the number of plastic cubes in the box. The second integer represents the player who starts - “0” means Lee Sedol starts the game and “1” means Garry Kasparov starts the game (0 and 1 are integers and are given in quotes only for clarity).
Output:
Each line of the output should either contain “Lee Sedol wins.” or “Garry Kasparov wins.” It is possible to determine a winner if both, Sedol and Kasparov play optimally
Quick Explanation
For every M, there exists an order of cubes that first player can select in order to win the game
Explanation
For M = 1,2 it is easy to understand the player starting the game wins.
For M > 2:
Assume there exists an M for which the first player loses the game even after playing optimally. This means that no matter what number he choses, the first player will lose. And this would be the case even with picking the plastic cube marked 1.
In the next turn, let the other player choose the cube marked x in order to win the game. This contradicts our hypothesis. If the first player had chosen x in his turn, he should win the game.
This proves that there does not exist an M for which the first player can lose the game by playing optimally.