Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
10880 – Colin and Ryan

El problema es de Teoría de números.
Lo que el problema dice es que tenemos una cantidad de galletas C y nos sobraron R galletas.
En la fiesta había G invitados y cada uno se comió Q galletas.
Y básicamente conociendo solamente cuantas galletas había y cuantas sobraron, hay que decir cuantas galletas se comió cada invitado.
El numero de invitados máximo puede ser C para que cada uno se comiera una galleta y mínimo 1, que implica que el único invitado se comió todas.
Para cada caso de entrada nosotros tenemos que decir todas las posibles soluciones.

Para el problema, tenemos 2 casos base.
Si la cantidad de galletas es igual al numero de galletas que sobraron, por lo tanto, cada invitado se comió 0 galletas.
Cuando el numero de galletas no es igual al numero de galletas que sobraron se puede hacer el siguiente razonamiento:

C = G*Q + R
C-R = G*Q
Q = C-R / G

Por lo tanto, como se puede observar, G es un divisor de C-R.
Así que la solución consiste en encontrar a los divisores de C-R.
Una vez calculados los divisores chacemos cuales de todos cumplen con la condición:

C%divisor[i] == R

Si la condición se cumple, entonces es una posible solución.
Hay que tener en cuenta que en algunos casos no hay solución.

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: