In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
A puzzle called "Tetris Attack" has lately become a very popular game in Byteotia. The game itself is highly
sophisticated, so we shall only introduce its simplified rules: the player is given a stack of elements, placed
one on another and marked with
different symbols. Exactly two elements of the stack are marked with each
symbol. A player's move consists in swapping two neighbouring elements, ie. interchanging them. If, as a
result of the swap, there are some two neighbouring elements marked with the same symbol, they are both
removed from the stack. Then all the elements that have been above them fall down in consequence and may
very well cause another removals. The player's goal is emptying the stack in the least possible number of
moves.
Write a programme that:
In the first line of the standard input there is one integer ,
.
The following
lines describe the
initial content of the stack. The
'th line contains one integer
-
the symbol which the
'th (
)
element from the bottom is marked with. Each symbol appears in the stack exactly twice. Moreover, no
two identical symbols neighbour initially. The test data is well chosen so that a solution with no more than
moves exists.
A solution with the minimum number of moves possible should be written out to the standard output as
follows. The first line should contain one integer -
the minimum number of moves. The following
should describe the optimal solution itself, i.e. a sequence of
integers
, one in each line.
denotes that in
'th move the player has chosen to swap the
'th
and
'th elements from the bottom.
If more than one optimal solution exists, your programme should write out any one of them.
For the input data:
5 5 2 3 1 4 1 4 3 5 2
the correct result is:
2 5 2
while for the input data:
3 1 2 3 1 2 3
the correct result is:
3 3 4 2
as well as:
3 4 3 2
Task author: Tomasz Walen.