Tarea 6 de Almacenamiento y Recuperación de la Información

Trimestre 2015 Otoño
Entrega: 23 de noviembre de 2015 a las 22:00.

Sean K y N dos enteros positivos. Supón que tienes K listas ordenadas de N elementos cada una y deseas obtener una lista ordenada con NK elementos y que para llevar a cabo esta tarea usarás el algoritmo del torneo visto en clase.

Escribe un programa torneoNN que muestre el estado del torneo después de una cierta cantidad de pasos, donde NN son los dos dí­gitos de la clave que le fue proporcionada por el profesor.

La entrada al programa estará en el archivo torneo.ent y consiste de un renglón con tres enteros K, N y P seguido de K renglones con N enteros positivos cada uno (cada renglón estará ordenado de menor a mayor y no habrá repeticiones). El entero P es la cantidad de pasos que debes llevar a cabo. Puedes suponer que 1 <= K <= 256 es una potencia de 2, que 1 <= N <= 1000, que cada uno de los enteros de las listas está entre 1 y 1,000,000 y que 0 <= P <= KN.

La salida del programa deberá estar en el archivo torneo.sal y consiste de log2 K renglones con K, K/2, ..., 2, 1 enteros cada uno, indicando cada una de las fases del torneo. Para indicar que una lista terminó y que por lo tanto ya no hay enteros a considerar debes usar el número -1. Observa que el -1 siempre pierde en las comparaciones.

Entrada 1
 Salida 1
 Entrada 2
 Salida 2
8 2 0
1 17
23 26
19 24
4 5
3 18
6 22
7 20
2 25
 1 4 3 2
1 2
1

 8 2 3
1 17
23 26
19 24
4 5
3 18
6 22
7 20
2 25		 17 4 6 7
4 6
4

Nota: los ejemplos de arriba coinciden con los ejemplos vistos en clase, excepto que estamos usando números en lugar de letras.