Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
12397 – Roman Numerals

Este problema es del tipo ad hoc.
Lo que nos piden es que dado el algún numero, nosotros digamos cuantos cerillos son necesarios para poder escribir ese numero en Romano.
Los números romanos solo utilizan 7 letras para representar sus números ( I, V, X, L, C, D, M ).
Para resolverlo, nosotros conocemos los casos base que son:
I = 1
V = 2
X = 2
L = 2
C = 2
D = 3
M = 4
Conociendo eso, nosotros podemos utilizar módulos para obtener las unidades, decenas, centenas y millares.
Conociendo esos 4 dígitos, nosotros podemos utilizarlo para contar cuantos cerillos son necesarios para el numero.
Por ejemplo, si nosotros quisiéramos formar el numero 378.
Podemos formar el 8 como la suma de los cerillos de 5 mas 3 veces el de 1.
Podemos formar el 7 como la suma de los cerillos de 50 mas 2 veces el de 10.
Podemos formar el 3 como 3 veces los cerillos de 100.
Podemos pre calcular los resultados para tener consultas en un tiempo O(1).
El proceso de pre calcular los resultados no toma mucho tiempo, ya que son solo números entre 1 y 3999, y eso es un rango muy pequeño de números.

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: