UVA 471 Magic Numbers

uva.onlinejudge.org/external/4/471.pdf

Hay varios problemas en los que es necesario trabajar en reversa. Este es uno de esos problemas. Un ataque frontal seria generar todos los posibles s1 (desde 1 hasta 9876543210 ya que no se pueden repetir los dígitos) y para cada s1, todos los posibles s2. Esta solución es imposible, ya que es necesitaría aproximadamente 10^18 operaciones. Y esto tomaría aproximadamente 31688 años, asumiendo que 1 operación tome 1 microsegundo!

La solución posible es generar todos los posibles s2, y dado que queremos encontrar los s1 tales que s1 / s2 = N, podemos despejar en esta ecuación, y generar todos los s1 = s2×N. Al hacer esto, podemos notar que s2×N no puede exceder 9876543210, ya que algún dígito se repetiría, por tanto solo tenemos que chequear desde 1 hasta 9876543210 / N.

Anuncios

Comentar

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 )

Google+ photo

Estás comentando usando tu cuenta de Google+. 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 )

Conectando a %s