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 (
#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.