Estrenando el euro
En enero de 2002 entró en circulación el euro en 12 Estados miembro de la Unión Europea. Se dio forma así a la eurozona que luego ha ido creciendo con la incorporación de más países.
La adopción del euro supuso el abandono de las monedas nacionales, como la peseta, el franco, el escudo o la lira. Acostumbrados hoy al pago por medios electrónicos, resulta curioso pensar que durante un par de meses de transición, la gente no solo llevaba billetes y monedas en los bolsillos sino que además eran de dos tipos distintos: las recién estrenadas monedas de euro y las anteriores, específicas del país.
En España hubo quien, tras comerse las tradicionales 12 uvas, salió corriendo en la madrugada del 1 de enero al cajero más cercano para poder tocar, por fin, los tan anunciados billetes de euro. Para conseguir ver las monedas hubo que esperar unas horas más, hasta poder comprar algo (una barra de pan, un portaminas o un kilo de cebollas) y que en la tienda devolvieran el cambio en la nueva moneda tal y como estaban obligados.
Paco Leccio Nista aún conserva, en la bolsa de unos grandes almacenes, el portaminas que se compró aquel día, junto con la vuelta que le dieron. Consiguió atinar en el precio de su compra de tal forma que le devolvieron una moneda de cada uno de los tipos existentes. Así pudo verlas todas a la vez. Aquellos brillantes trozos de metal indicaban que el futuro ya había llegado.
Entrada
Cada caso de prueba comienza con un número 1 ≤ n ≤ 5.000 indicando cuántos tipos de monedas existen en un determinado sistema monetario. A continuación aparecen n números ordenados de menor a mayor con el valor de cada tipo. Se garantiza que ninguna moneda tiene un valor superior a 109.
La entrada termina con un caso sin monedas, que no debe generar salida.
Salida
Por cada caso de prueba se escribirá la máxima cantidad de monedas de tipos distintos que se puede conseguir con una única compra, sabiendo que la persona que atiende devuelve el cambio usando las monedas más altas posibles. Por ejemplo, si los tipos de moneda fueran 2, 7 y 10, y la vuelta fuera 14, el tendero nos daría primero una moneda de 10, por ser la más alta que puede darnos, y luego dos monedas de 2. Este procedimiento lo sigue incluso aunque eso le impida devolver una cantidad, como ocurriría con 11 en el ejemplo.
Entrada de ejemplo
8 1 2 5 10 20 50 100 200 4 2 4 6 10 0
Salida de ejemplo
8 3