MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Latin American Regional Contest - 2007

Ended

D - Drop the Triples

Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)

The inhabitants of a small Caribbean island in the region known as Bermuda’s Triangle love to spend their warm summer nights playing cards. As a tribute to the region where they live, all of their card games have some connection to triangles. One of the most popular games in the island is known as Triples, and has very simple rules.

The game is played between two players, with a set of standard playing cards. Cards are distinguished only by their values, from $1$ (Ace) to $13$ (King). The cards are shuffled and placed as a pile in the center of the table, face down. This pile is called the stock. The two players take turns at playing. At each turn, a player

  • draws the top card from the stock, adding it to her/his hand; and
  • decides whether she/he wants to “drop some triples”.

Dropping a triple consists of choosing three cards (a triple) from the hand and placing them on the table, face up. The dropped triples stay on the table until the end of the game. Only some sets of three cards form a valid triple. There are two types of valid triples:

  • Perfect triples are made of three cards whose values represent the length of sides of an equilateral triangle;
  • Common triples are made by three cards whose values represent the length of sides of any other (not equilateral) triangle.

The figure below shows examples of perfect triples (a), common triples (b), and invalid triples (c).

Only valid triples can be dropped, but a player may drop any number of triples at a given turn. In particular, since players know the number of cards in the stock at every turn, a player may decide to drop all triples in her/his last turn. Some players, however, normally drop some triples during the game, to maintain as few cards in their hands as possible.

The game finishes when the stock is empty. The winner is the player that dropped the largest number of perfect triples. If both players dropped the same number of perfect triples, the winner is the player that dropped the largest number of common triples. If both players dropped the same number of perfect triples and the same number of common triples, the result is a tie.

Given the description of the cards in the stock, write a program that determines the winner of a game of Triples, considering both players play as best as possible.


Input

The input contains several test cases. The first line of a test case contains one integer $N$ representing the number of cards in the stock $(6 \leq N \leq 10^4)$. The next line contains $N$ integers $X_i$, separated by single spaces, representing the cards in the stock $(1 \leq X_i \leq 13$, for $1 \leq i \leq N)$. The cards are given in the order they are drawn by the players: the first card in the input ($X_1$) is the first card drawn, the second card in the input ($X_2$) is the second card drawn, and so on. Several cards with the same value may be present in the stock, and not necessarily all card values are present in the stock. The end of input is indicated by $N = 0$.

The input must be read from standard input.

Output

For each test case your program must output a single line, containing $\texttt{‘1’}$ if the first player to play wins the game, $\texttt{‘2’}$ if the second player wins, or $\texttt{‘0’}$ if there is a tie.

The output must be written to standard output.

Sample test(s)

Input
7 5 6 5 6 5 6 8 12 13 13 13 13 13 13 1 3 2 9 3 9 12 1 2 1 2 1 2 3 1 4 2 5 3 0
Output
0 2 1