3925 - Towers

Created by Marcelo Fornet Fornés
Added by MarX (2017-07-06)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Adam and Bob are bored of games where they compete against each other. Today, their mother designed a one-player game, where they will cooperate with one another.

The game consists of a board with exactly 12 cells in a row. In the first cell (the leftmost one), their mother placed a stack of N coins with different sizes. Adam and Bob need to move all the coins to the last cell (the rightmost one) such that the coins are piled onto a stack, sorted by their sizes, where the largest coin is at the bottom of the stack (i.e. if we look at the stack from top to bottom, the coins are sorted from smallest to largest). The only operation the boys are allowed do is to remove the coin in the top of one stack and place it on top of the next adjacent stack (the one to its immediate right). Notice that this operation cannot be executed when the stack is empty or the coin is already on the rightmost cell.

Since they are only familiar with games where they play against each other, Adam and Bob are having trouble coming up with a strategy to beat this game. Help them find any valid sequence of moves to reach their goal.
Adam y Bob están cansados de los juegos donde ellos compiten uno contra el otro. Hoy, su madre diseñó un juego de un solo jugador, donde ellos cooperarán entre sí.

El juego consiste en un tablero con exactamente 12 celdas en fila. En la primera celda (el del extremo izquierdo), su madre coloca una pila de N monedas con distintos tamaños. Adam y Bob necesitan mover todas las monedas hasta la última celda (la del extremo derecho) tal que esas monedas están en una pila ordenadas por sus tamaños, donde la moneda más grande se encuentra en el fondo de la pila y (es decir, si miramos la pila desde arriba hacia abajo, las monedas están ordenadas de menor a mayor tamaño). La única operación permitida a los chicos es quitar la moneda del tope de la pila y colocarla en el tope de la siguiente pila adyacente (o sea, la pila que le sigue a su derecha). Note que esta operación no se permite cuando la pila está vacía ni cuando la moneda ya está en la última celda de la derecha.

Como Adam y Bob solo conocen de juegos donde compiten entre sí, ellos tienen serias dificultades en encontrar una estrategia para completar el juego. Ayúdalos a encontrar una secuencia válida de movimientos que les permita alcanzar su objetivo.
;jsessionid=5824317BC415BEB70AFB21556A540B95
Adam and Bob are bored of games where they compete against each other. Today, their mother designed a one-player game, where they will cooperate with one another.

The game consists of a board with exactly 12 cells in a row. In the first cell (the leftmost one), their mother placed a stack of N coins with different sizes. Adam and Bob need to move all the coins to the last cell (the rightmost one) such that the coins are piled onto a stack, sorted by their sizes, where the largest coin is at the bottom of the stack (i.e. if we look at the stack from top to bottom, the coins are sorted from smallest to largest). The only operation the boys are allowed do is to remove the coin in the top of one stack and place it on top of the next adjacent stack (the one to its immediate right). Notice that this operation cannot be executed when the stack is empty or the coin is already on the rightmost cell.

Since they are only familiar with games where they play against each other, Adam and Bob are having trouble coming up with a strategy to beat this game. Help them find any valid sequence of moves to reach their goal.

Input specification

The first line consists of an integer N (1 ≤ N ≤ 1000), the number of coins placed on the stack in the leftmost cells at the start of the game.

The next N lines describe the initial content of the stack in the leftmost cell, given in the order from the topmost coin to the bottommost. The i-th of these N lines has an integer representing the size of the i-th coin in the stack. All sizes are integers between 1 and N and there are not two coins with the same size.
La primera línea consiste en un número entero N (1 ≤ N ≤ 1000), la cantidad de monedas colocadas en la pila de la primera celda al inicio del juego.

Las próximas N líneas  describen el contenido inicial de la pila en la primera celda,  dado en el orden de la moneda que se encuentra en la cima de la pila hasta la moneda en el fondo de la misma. La i-ésima de esas N líneas contiene un entero representando el tamaño de la i-ésima moneda en la pila. Todos los tamaños son números enteros entre 1 y N y no existen dos monedas con el mismo tamaño.
The first line consists of an integer N (1 ≤ N ≤ 1000), the number of coins placed on the stack in the leftmost cells at the start of the game.

The next N lines describe the initial content of the stack in the leftmost cell, given in the order from the topmost coin to the bottommost. The i-th of these N lines has an integer representing the size of the i-th coin in the stack. All sizes are integers between 1 and N and there are not two coins with the same size.

Output specification

If there is no valid solution, print -1. Otherwise, construct and print a valid solution that satisfy all given restrictions in the following format:
  • First, print integer M representing the number of moves to perform.
  • Then, print M integers between 1 and 11, which describe the sequence of operations to be performed. Each printed integer k denotes the operation where we take the coin from the top of the stack on the k-th cell and place it on top of the stack on the (k+1)-th cell.  You may separate the integers by spaces, newlines or a mix of both.
If there are multiple ways to beat the game, you may print any valid sequence that accomplishes this task.
Si no existe solución válida, imprima -1. De lo contrario, construya e imprima una solución válida que cumpla las restricciones dadas.  Imprima en el siguiente formato:
  • Primero, imprima un número entero M representando la cantidad de pasos a ejecutar.
  • Luego, imprima M números enteros entre 1 y 11, los cuales describen la secuencia de operaciones a ejecutar. Cada número entero k que imprimas corresponde a la operación donde tomamos la moneda del tope de la pila en la celda k-ésima celda y la colocamos en el tope de la pila de la (k+1)-ésima celda.  Imprima los números en líneas distintas, separadas por espacios, o una mezcla de ambos.
En el caso de múltiples soluciones, puedes imprimir cualquier secuencia válida que logre completar el juego.
;jsessionid=5824317BC415BEB70AFB21556A540B95
The first line consists of an integer N (1 ≤ N ≤ 1000), the number of coins placed on the stack in the leftmost cells at the start of the game.

The next N lines describe the initial content of the stack in the leftmost cell, given in the order from the topmost coin to the bottommost. The i-th of these N lines has an integer representing the size of the i-th coin in the stack. All sizes are integers between 1 and N and there are not two coins with the same size.

Sample input

2
2
1

Sample output

22
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11

Hint(s)