1143 - Drop the Triples:: HUST Online Judge

1143 - Drop the Triples

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 11

Solved: 1

Description

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 shuﬄed 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 ﬁgure 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 ﬁnishes 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 ﬁrst line of a test case contains one integer N
representing the number of cards in the stock (6 ≤ N ≤ 104
). The next line contains N
integers Xi, separated by single spaces, representing the cards in the stock (1 ≤ Xi ≤ 13, for
1 ≤ i ≤ N). The cards are given in the order they are drawn by the players: the ﬁrst card
in the input (X1) is the ﬁrst card drawn, the second card in the input (X2) 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 ‘1’ if the ﬁrst player to
play wins the game, ‘2’ if the second player wins, or ‘0’ if there is a tie.
The output must be written to standard output.

sample 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

sample output

0
2
1

hint

source