Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
11385 – Da Vinci Code

El problema es sencillo. Dado una cadena codificada hay que decodificarla.
En la decodificacion, nos indica que hace uso de los numeros de fibonacci y a que indice hace referencia ese numero.
Para la comprension del problema, se ejemplificara con uno de los ejemplos de entrada.

11
13 2 89 377 8 3 233 34 144 21 1
OH, LAME SAINT!

El primer numero, en este caso 11, nos indica que vendrán 11 números de fibonacci, cada uno de estos estará asociado a una letra.
Seguido de un renglón, que contendrá la cadena codificada.
Para la de-codificación de la cadena, no se toman en cuenta cualquier otro carácter que no sea letra.

entonces tenemos que, la cadena queda asociada a los números de fibonacci de la siguiente manera:

0 13
H 2
L 89
A 377
M 8
E 3
S 233
A 34
I 144
N 21
T 1

Y lo que hay que hacer es re ordenar los números de manera creciente, quedando lo siguiente:

T 1
H 2
E 3

M 8
0 13
N 21
A 34

L 89
I 144
S 233
A 377

Como se podrán percatar, los espacios se colocan en el lugar donde la secuencia de fibonacci se pierde, como después de la palabra “THE”, la letra E tiene asociado 3, y la M de la palabra “MONA” tiene asociado el numero 8.
Es fácil notar que si la secuencia de los números de fibonacci no se va cumpliendo, es necesario agregar un espacio, hasta llegar al numero siguiente, por ejemplo

3
2 3 5
A B C

La salida correspondiente a ese caso de prueba es:
_ABC
Donde _ representa un espacio. Ese espacio se coloco debido a que no se cuenta con el numero 1 en la secuencia. Asi, si tuvieramos lo siguiente:

3
3 5 8
A B C

Su salida seria
__ABC

Ya que los primeros 2 números de fibonacci están ausentes en la codificación de la cadena.
Para esto basta con pre calcular los números de fibonacci, ya que nos aseguran que el numero no va a ser mas grande que 2^31 y el fibonacci que cumple esta condifcion es el numero 46.

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: