Problem F
Game of Euler
Input: Standard Input
Output: Standard Output
Time Limit: 3 Seconds
The Game of Euler is played between two players
on a 4x4 board. The board is initially empty. The players alternatively put
pins of different lengths on the board. You can either put them from one of the
sides, in which case the pin will cover the same number of squares as the
length of the pin (1, 2 or 3), or you can put it perpendicular to the board
(pushing it straight down), covering exactly 1 square. A pin may only cover
squares that are not covered already. The player who puts the last pin, and
thus makes all 16 squares covered, loses. Both players have an infinite supply
of pins of length 1, 2 and 3.
Consider the position in the picture to the right. If the player to move covers one of the two squares in either corner, the opponent will cover both squares in the opposite corner, so the first player will have only one move and will thus lose. But if the first player covers both squares in one corner, the opponent will cover only one square in the other corner, winning again. So the first player will lose the game no matter what move he makes. We say that such a position is losing for the player to move, because no matter which move he makes, he will lose the game if the opponent plays "perfectly" (that is, make the best moves). If the position is not losing, it is winning. Since fewer and fewer squares remains uncovered as the play progresses, the game will always end with a loser and a winner (never a draw).
Input
The first line in the input contains an integer N the number of test cases to follow (N < 100,000). Each test case contains of 4 lines, each line containing four character. These lines represent which squares of the board have been covered so far. A covered square is indicated by a 'X', an uncovered square is indicated by a '.'. At least one square on the board will be uncovered. Each test case is preceded by a blank line.
Output
For each test case output a single line containing either "LOSING" or "WINNING" depending on whether the position is losing or winning for the player to move.
3
XXX. XXX. .XXX .XXX
XXXX ...X XX.X XX.X
.... .... .... .... |
LOSING WINNING LOSING
|
Finaly, some "history" about the Game of Euler. It contains no information vital for solving the
problem, so you may skip it if you want.
"The
origin of the game is hidden in a distant past. One does know that it was used
in ancient
Many
philosophers of ancient
Knowledge of
the deeper meaning of the game and insights on how to play to win were the criteria used to qualify for membership in a group
called The Wise Men. The group never became larger than seven and it came to be
known as The Seven Wise Men. After the decline of
Next time the
game surfaces is during the plundering of Montezuma I's
tomb in Tenochtitlán. The Conquistadors led by Hernan Cortez discovered a pierced block made of solid
gold. The block's function was never understood and it was melted together with
the rest of the gold. We know this today because the soldier
who discovered the block Juan Rodriguez, was so intrigued by it that he made
notes on its form and size. The block departed from all the other loot, both in
form and function. Juan was the only person to be spared the very painful
stomach disease that eventually killed all other conquistadors that had touched
the block. The stomach pain became known as Montezuma's revenge. The notes were
passed on from generation to generation in the Rodriguez family before they
were made public. Even more remarkable is the fact that the dimensions of the
Aztec block exactly matches the dimensions used in ancient
The game remained unknown until Leonhard
Euler reinvented the game. It is believed that knowledge of the game could have
survived from classical antiquity in certain very secret orders, possibly among
the Rosenkreutz and probably in another even more
secret order. The name of this group is not known to this day and its existence
is still disputed. Theory has it that the society can trace its roots to the
Nubians, a people that lived by the water of the
The society can
be traced in the Egyptian kingdom before it reaches
The order is
led by a person called the Head. Only the sharpest and wisest brains can be
selected for membership. Nothing indicates that the purpose of the group should
be anything but good. Its probable cause is to further the development of the
human species. Some say that Leonhard Euler was a
member and that by revealing the game he was excluded. It is believed that both
Neumann was
probably the best player of all times if you exclude the best of the Yanco tribe. The Yanco tribe was
discovered to the rest of the world by anthropologist Franz Boas. The tribe
lives in the inner of the Amazons. The Yanco people
have a game that is very similar to the classical but their game has 6x6, 7x7
or even up to 10x10 units. The Yancos unsurpassed
skill is based solely on intuition. Their counting ability is low; the number
three in Yanco language is called poettarraroincoaroac.
Researchers that have visited the Yanco say that the
number four is met by expressions of total confusion. They call the game Maua-maui, the dream-game and only the elders are allowed
to play. To the other members it is taboo. The game is only used under
religious ceremonies and the playing is preceded by complicated rituals to
appease the game God.
All these
stories about the game and the society could be pure imagination. It might be
yet another trivial game and maybe not..."