Extrañas monedas (nivel 2)

Enunciado

Pagar diversas monedas puede ser entendido como sumarlas, y que nos devuelvan, como restar. Así conseguimos trasmitir dinero (miguelhernandios, en nuestro caso).

Nos encontramos con un caso similar al del problema primero, o el sexto de los de primer ciclo. Sumas y restas de números enteros, que persiguen conseguir una cantidad determinada. Las cantidades que utilizamos en esta ocasión son 10, 12 y 15, cuyo máximo común divisor es 1. Por eso, sabemos que podemos conseguir cualquier múltiplo de 1, es decir, cualquier número (ver la solución al problema primero de primer ciclo).

Aunque no conozcamos estos ejemplos, podemos encontrar fácilmente una combinación que proporcione las cantidades que nos piden (3, 7 y 11). Pagando 15 y devolviendo 12 cambiamos 3, pagando 12 y 15 y devolviendo dos de 10 cambiamos 7 y, por ejemplo, pagando tres de 15 (45) y cobrando una de 10 y dos de 12 (34) obtenemos 11.

Como nos piden la mejor forma de obtener ciertos cambios, podemos probar combinaciones de pocas monedas hasta lograr todos los cambios que se quieren. De esta forma, nos aseguramos que son los mejores cambios.

Con una sola moneda no podemos lograr ninguna transferencia de 1 a 6 miguelhernandios.

Con dos monedas, restando una de otra, podemos lograr 2 (12 - 10), 3 (15 - 12) y 5 (15 - 10), que son todas las combinaciones que dan valores pequeños.

Con tres monedas no se puede hacer mucho, ya que sumando 10 + 10 - 15, que es la combinación más pequeña, ya da 5, que se logra con sólo dos monedas. La siguiente combinación es 10 + 12 -15, que da 7 (por cierto, mejora la forma de obtener 7 que vimos antes).

Con cuatro monedas, tenemos 12 + 12 - 10 - 10, que da 4. 15 + 15 - 12 - 12, que da 6 y 10 + 15 - 12 - 12, que nos da 1.

Así, tenemos las mejores combinaciones para los 6 primeros valores:

1 = 10 + 15 - 12 - 12

2 = 12 - 10

3 = 15 - 12

4 = 12 + 12 - 10 - 10

5 = 15 - 10

6 = 15 + 15 - 12 - 12

Por último, es evidente que podrán pagar cualquier cantidad, ya que pueden transferir un sólo miguelhernandio, por lo que uno a uno pueden pagar cualquier cifra entera.