I Copa UHEnded |
Fito lleva varios días ayudando en una paladar asignado como cajero. El dueño de la paladar desea que toda cantidad de dinero que se devuelva a un cliente se haga con la menor cantidad de monedas posibles. Él ha notado que Fito resuelve este problema aplicando el clásico algoritmo greedy, es decir devolviendo siempre la moneda de mayor valor mientras sea posible. Luego de observar por un rato el comportamiento de Fito, el dueño le explicó que esta estrategia no siempre daba el óptimo, pero no resultó muy convincente. El objetivo de este problema es ayudar a Fito a comprender lo que intentaba explicarle su jefe.
Dado los tipos de monedas que hay en la caja, usted debe determinar si la estrategia de Fito es correcta, es decir si en todo momento devuelve la solución óptima con esas denominaciones. Si este no es el caso, entonces el programa debe determinar el menor valor $S$ para el cual la estrategia de Fito resulta fallida.
Línea 1
: Un entero $N$ $(1 \le N \le 1000)$, la cantidad de monedas en la caja.
Línea 2
: $N$ enteros diferentes separados por espacio $d_1, d_2, ..., d_N$ $(1 \le d_i \le1000)$, los valores de las monedas en la caja. Asuma que siempre está la moneda de valor 1 y hay infinitas monedas de cada valor.
Línea 1
: Imprima “Fito”, si su algoritmo siempre encuentra la menor cantidad de monedas. De lo contrario imprima el menor valor $S$ para el cual Fito cambia $S$ en más monedas que la forma óptima.
Hint
Primer Ejemplo
Si Fito tiene que devolver un total de 6 unidades, entonces comenzará con la moneda de valor 4, luego 1 y después 1. No obstante, con dos monedas de valor 3 se obtiene un mejor resultado.
Segundo Ejemplo
El algoritmo de Fito es
óptimo con ese tipo de monedas
.