Tarea 5 de Almacenamiento y Recuperación de la
Información
Trimestre 2008 Primavera
Entrega: 18 de agosto de
2008 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. Página de prueba.
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.