Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
11371 – Number Theory for Newbies

El problema es de tipo Ad hoc.
Lo que nos dan es un numero n, y lo que nos piden es encontrar una forma de re ordenar el numero de tal manera que su diferencia sea máxima y la diferencia sea múltiplo de 9.
El numero máximo que nos dan tiene a lo mas 10 dígitos (2000000000), por lo tanto, podemos sacar todas las permutaciónes utilizando next_permutation.
Al ir obteniendo las permutaciónes podemos ir obteniendo modulo 9 de cada numero, e ir guardando el máximo y el mínimo de entre los números que tengan el mismo modulo.
La explicación es que si dos números tienen el mismo modulo los podemos representar de la forma
A = 9*q1 + r
B = 9*q2 + r

Donde q es un entero.
y cuando hagamos la diferencia entre ellos tendremos
A-B = 9*q1 +r – 9*q2 -r = 9*q1 – 9*q2 = 9*(q1 – q2)

Por lo tanto, si tienen el mismo residuo, la diferencia es un múltiplo de 9.
Uva vez realizas todas las permutaciónes, elegimos entre los que almacenamos el que nos maximice la diferencia.
Solo hay que tener en cuenta algo al ir generando las permutaciónes, y es que hay que cuidar que no tenga ceros a la izquierda, ya que si los tiene, no se tiene que considerar.

Codigo 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: