Juego con matrices
Durante la Olimpiada de Informática de Centroamérica y el Caribe (OICC), los organizadores quieren proponer un juego para los participantes.
El juego consiste en transformar una cuadrícula en otra utilizando la menor cantidad posible de movimientos. Se tienen dos cuadrículas de tamaño , ambas contienen los enteros del
al
, cada uno exactamente una vez, pero posiblemente en posiciones diferentes.
Para modificar una cuadrícula se permite realizar una de las siguientes operaciones cualquier número de veces (es posible no realizar ninguna operación):
- Intercambiar dos filas.
- Intercambiar dos columnas.
El objetivo del juego es transformar la primera cuadrícula en la segunda utilizando la menor cantidad posible de operaciones.
Entrada
La primera línea contiene un entero (
)
el tamaño de las cuadrículas.
A continuación, se describen las filas de la primera cuadrícula, cada una con
enteros.
Finalmente, se describen las filas de la segunda cuadrícula, siguiendo el mismo formato.
Se garantiza que ambas cuadrículas contienen los enteros del al
, cada uno exactamente una vez.
Salida
Imprime un entero
la mínima cantidad de operaciones necesarias para transformar la primera cuadrícula en la segunda.
A continuación, imprime líneas que describan las operaciones realizadas.
Cada operación debe tener uno de los siguientes formatos:
1 a b: intercambiar las filasy
.
2 a b: intercambiar las columnasy
.
Las filas y columnas están numeradas desde hasta
.
Si no es posible transformar la primera cuadrícula en la segunda utilizando las operaciones permitidas, imprime únicamente .
Subtareas
Esta tarea está compuesta por subtareas.
La puntuación de cada subtarea se determina de la siguiente manera:
- Se otorgará el
de los puntos si se proporciona una secuencia válida de operaciones que transforme la primera matriz en la segunda utilizando la cantidad mínima de operaciones, en todos los casos de prueba de la subtarea.
- Se otorgará el
de los puntos si la cantidad de operaciones indicada es correcta en todos los casos de prueba de la subtarea, independientemente de que la secuencia de operaciones sea válida.
- Se otorgarán
puntos en caso contrario.
| Subtarea | Puntos | Restricciones adicionales | Dependencias |
|---|---|---|---|
| Sin restricciones adicionales |
Ejemplos
Entrada 1
3
1 2 3
4 5 6
7 8 9
2 1 3
8 7 9
5 4 6
Salida 1
2
2 1 2
1 2 3
Entrada 2
3
6 3 7
8 1 4
9 2 5
8 5 2
7 3 1
9 4 6
Salida 2
-1
Comments