3D Game Of Thrones
Practice
0 (0 votes)
Algorithms
Game theory
Medium
Problem
34% Success 217 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

The two renowned houses of the Seven Kingdoms - The Starks & The Lannisters have a rather dull relationship. "The Lannisters always pays their debts" - says Tywin, the Head of the Lannisters, while the Starks, under the leadership of Jon Snow, are looking for a revenge of the Red Wedding. They both hate each other a lot, and so they decided to play a game to decide who will sit on the Iron Throne.

There are N objects in the kingdom (initially all are cuboids). Each object has different dimensions (Ai, Bi, Ci) and can be realized as composed of smaller identical unit cubes. There is an Iron Throne replica on (Ai, Bi, Ci) of each object initially (See image below). The game is played in turns. The Starks, known for their nobility always play first. In each turn, the concerned House does the following:

  • He takes one of the objects in the game and places it in the corner of a room.

  • He pushes (or compresses) the object in one of the direction of the axes, X, Y or Z (see sample test case image). So if the object he selected has its current dimensions as (p, q, r), then he can select X axis if p > 0, Y axis if q > 0 and Z axis if r > 0. Once he has decided the direction , he chooses a number s > 0 and pushes that dimension s units. So for example if he had chosen the X axis, whose value is p, then he can choose any number s (0 < s <= p), and make p = p - s for that direction

  • If the object becomes a point mass, i.e. it has come to state (A, B, C) = (0, 0, 0), then it is thrown out of the game.

The House that cannot make a move loses the game( and also the Iron Throne). Given N and the dimension of each object initially, you need to predict the winner.

Input & Output:

The first line contains the number of test cases T. Description of the T test cases follow. The first line of every test case contains N, the number of objects. The next N lines contains A B C the dimensions of each object initially.

For each test case you need to print the winner of the game, "Stark" or "Lannister". (quotes for clarity)

Constraints: 1 <= T <= 125000
1 <= N <= 20
1 <= Ai, Bi, Ci <= 50

enter image description here

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
1 votes
Tags:
MediumAlgorithmsMathematicsOpenApprovedGame Theory
Points:30
Tags:
MediumAlgorithmsMathematicsOpenApprovedGame Theory
Points:30
1 votes
Tags:
MathematicsMediumGame TheoryNumber Theory
Editorial

No editorial available for this problem.