Want to try solving this problem? You can submit your code online if you log in or register.

Have you ever heard of Melodramia, my friend? It is a land of forbidden forests and boundless swamps, of sprinting heroes and dashing heroines. And it is home to two dragons, Rose and Scarlet, who, despite their competitive streak, are the best of friends.

Rose and Scarlet love playing *Binary Snap*, a game for two players. The
game is played with a deck of cards, each with a numeric label from 1 to
*N*. There are two cards with each possible label, making 2*N* cards in
total. The game goes as follows:

- Rose shuffles the cards and places them face down in front of Scarlet.
- Scarlet then chooses either the top card, or the second-from-top card from the deck and reveals it.
- Scarlet continues to do this until the deck is empty. If at any point the
card she reveals has the same label as the previous card she revealed, the
cards are a
*Dragon Pair*, and whichever dragon shouts `Snap!' first gains a point.

After many millenia of playing, the dragons noticed that having more possible Dragon Pairs would often lead to a more exciting game. It is for this reason they have summoned you, the village computermancer, to write a program that reads in the order of cards in the shuffled deck and outputs the maximum number of Dragon Pairs that the dragons can find.

The first line of input will contain a single integer, *N*. The following
2*N* lines will each contain an integer, *v*_{i} (where 1
≤ *v*_{i} ≤ *N*), representing the label of the
*i*th card from the top of the shuffled deck.

Output should consist of a single integer: the maximum number of Dragon Pairs Scarlet can deal in a game of Binary Snap with the deck in the given order.

4 1 4 1 2 3 2 3 4

3

We can make Dragon Pairs from all of the cards except the 4s with the following sequence of moves:

`1 4 1 2 3 2 3 4`: The deck of cards we are given, first we deal the top ``1`' from the deck.`4 1 2 3 2 3 4`: Next we deal the ``1`' from second top position in the deck. This gives us a Dragon Pair.`4 2 3 2 3 4`: Next we deal the ``4`' from the top.`2 3 2 3 4`: Next we deal the ``2`' from the top.`3 2 3 4`: Next we deal the ``2`' second from the top. This gives us another Dragon Pair.`3 3 4`: Next we deal the ``3`' from the top.`3 4`: Next we deal the ``3`' from the top. This gives us another Dragon Pair.`4`: Finally we deal the ``4`' from the top.

This gives us 3 Dragon Pairs in total, so we must output 3.

For all subtasks,
1 ≤ *N* ≤ 100 000.

- For Subtask 1 (30 marks),
*N*≤ 10. - For Subtask 2 (20 marks),
*N*≤ 100 and cards with the same labels are*at least*3 spaces apart (i.e. if*v*_{i}=*v*_{j}, then |*i*-*j*| ≥ 3). - For Subtask 3 (20 marks),
*N*≤ 100. - For Subtask 4 (30 marks), there are no further constraints.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 22 September 2021, 11:29am AEST