Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
400 – Unix ls

El problema es de Ordenamiento relacionado también con el formato de salida.
En linux existe el comando ls, así que en este caso nos piden eso.
Dada una lista de archivos, hay que ordenarla e imprimirla.
Para el ordenamiento podemos usar quicksort que es la parte sencilla del problema.

Para el formato de salida nos dan unas restricciones:

  • Las columnas tendrán el tamaño de la cadena mas larga mas 2
  • Tendremos que usar el mayor numero de columnas posibles
  • Hay que poner espacios que falten incluso para la ultima columna para a completar el tamaño

Ejemplo:

10
tiny
2short4me
very_long_file_name
shorter
size-1
size2
size3
much_longer_name
12345678.123
mid_size_name

En este caso tenemos que el nombre del archivo mas largo es very_long_file_name, con una longitud de 19, por lo tanto cada columna tendrá 21 caracteres.
Para determinar cuantas columnas, lo podemos hacer con una división, que seria 62 entre el numero de caracteres que tiene la columna. El 62 lo obtenemos como la suma de los 60 caracteres máximo por renglón mas los 2 espacios que hay que agregarle a la cadena mas larga.

En este caso son 21 caracteres por columna, por lo tanto tendremos 62/21, que es 2.
Para determinar cuantas filas vamos a tener, basta con otra división que es el numero de elementos que tenemos entre el numero de columnas, pero a esto hay que sacarle cielo (ceil).
Para el ejemplo anterior tenemos que son 10 elementos dividido entre el numero de columnas que son 2, obtenemos 5.
En el primer caso la división da entera, pero observemos el ultimo caso:
Ejemplo:

19
Mr._French
Jody
Buffy
Sissy
Keith
Danny
Lori
Chris
Shirley
Marsha
Jan
Cindy
Carol
Mike
Greg
Peter
Bobby
Alice
Ruben

Tenemos que son 5 columnas y son 19 archivos. Por lo tanto tendriamos que son 19 dividido entre 5 filas, lo que nos da 3.8.
El 0.8 sobrante quiere decir que van a sobrar columnas para los archivos.
Acá es importante no colocar espacios de mas, ya que seria incorrecto:
La salida correcta es:

------------------------------------------------------------
Alice_______Chris_______Jan_________Marsha______Ruben       
Bobby_______Cindy_______Jody________Mike________Shirley     
Buffy_______Danny_______Keith_______Mr._French__Sissy       
Carol_______Greg________Lori________Peter

Donde el _ representa el espacio.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: