Canvi mínim P81009


Statement
 

pdf   zip

thehtml

Donada una quantitat c, i n valors diferents de monedes, de cadascun dels quals se’n disposa de tantes com es vulgui, calculeu quin és el mínim nombre de monedes que sumen canvi c. Per exemple, si c = 20 i podem triar entre els valors 2, 4, 6 i 17, es pot aconseguir c només amb quatre monedes: 2 + 6 + 6 + 6 = 20.

Entrada

L’entrada consisteix en diversos casos, cadascun amb c i n, seguits d’n naturals diferents entre 1 i 104. Suposeu que c està entre 0 i 104, i que n està entre 1 i 1000.

Sortida

Per a cada cas, escriviu el mínim nombre de monedes que tenen suma c. Si no n’hi ha cap, escriviu “no”.

Public test cases
  • Input

    20 4  2 4 6 17
    15 4  2 4 6 17
    0 1  10000
    1000 3  600 1000 400
    

    Output

    4
    no
    0
    1
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python