COCI '23 Contest 5 #5 Trokut

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Ivan and Lucija are on a journey to a place far... far away. They know that the journey will last a long time and that they will be bored at some point. While they were thinking about what to do, Lucija came up with a game.

She drew N points on paper so that they form the vertices of a regular N-gon and labeled them sequentially from 1 to N. The player whose turn it is selects two of the drawn N points such that the line segment connecting those two points does not intersect any of the previously drawn line segments and connects those two points. Line segments are allowed to touch at vertices. A player wins if after their move there exist three connected line segments forming a triangle, i.e., if there exist three points such that they are all connected by the drawn line segments. Of course, players are allowed to connect adjacent vertices, and those line segments are considered for triangle formation. Players take turns, and Lucija is the first to play.

Both are extremely skilled players, and we know they will play optimally. Your task is to determine, for a given N, who will be the winner of the game. It can be shown that the game will always end after a finite number of moves and that there will always be a winner.

Input Specification

In the first row there is an integer T (1 \le T \le 10\,000), the number of scenarios.

In the next T rows there is an integer N (3 \le N \le 10^9), the number of points Lucija drew on the piece of paper.

Output Specification

In T rows, for every scenario in the given order, output Ivan or Lucija, the winner in the given scenario.


Subtask Points Constraints
1 13 T \le 18, N \le 20
2 36 T \le 998, N \le 1\,000
3 15 N \le 10^5
4 46 No additional constraints.

Sample Input 1


Sample Output 1


Explanation for Sample 1

When N = 3, then all three possible line segments must be connected, and Lucija wins. When N = 4, then Lucija can connect the line segment between points 1 and 3. We see that after any move by Ivan, Lucija can connect a triangle and win.

Sample Input 2


Sample Output 2



There are no comments at the moment.