Canvi quasi-mínim P93457


Statement
 

pdf   zip

thehtml

La caixa d’una botiga disposa d’un nombre il·limitat de monedes de cada tipus (en euros). Per a cada canvi, el caixer voldria retornar el mínim nombre de monedes que tingui aquella suma, però a vegades s’atabala i no ho aconsegueix.

En aquest problema, direm que un canvi és quasi-mínim si el caixer fa servir com a molt una moneda més del que és estrictament necessari. Feu un programa que determini si diversos canvis donats són quasi-mínims o no.

Entrada

L’entrada consisteix en diversos casos, cadascun amb un natural n entre 1 i 1000, seguit d’n ‍valors de monedes, tots escollits entre 1, 2, 5, 10, 20, 50, 100 i 200. (Els valors de les monedes estan expressats en cèntims d’euro.)

Sortida

Per a cada cas, escriviu “si” si el canvi donat és quasi-mínim, i “no” altrament.

Public test cases
  • Input

    2  1 5
    3  2 2 2
    4  2 1 2 1
    1  200
    5  200 50 200 50 20
    5  200 50 200 50 100
    5  200 20 20 200 200
    

    Output

    si
    si
    no
    si
    si
    no
    si
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python