Canvi mínim (2) X23961


Statement
 

pdf   zip

Donada una quantitat cc, i nn valors diferents de monedes, de cadascun dels quals se’n disposa de tantes com es vulgui, calculeu una manera de sumar canvi cc amb el mínim nombre de monedes. Si hi ha diferents solucions, escolliu aquella que usa la moneda de més valor més vegades; en cas d’empat, la que usa la següent moneda de més valor més vegades; etc. Per exemple, si c=6c = 6 i podem triar entre els valors 1, 3, 5, es pot aconseguir cc amb només dues monedes: fent 1+5=61 + 5 = 6, i també 3+3=63 + 3 = 6. De les dues maneres, la primera usa més monedes de valor 5 que la segona, i per tant seria la que voldríem.

Entrada

L’entrada consisteix en diversos casos, cadascun amb cc i nn, seguits d’nn naturals diferents ordenats de forma creixent entre 1 i 10410^4. Suposeu que cc està entre 1 i 10410^4, i que nn està entre 1 i 1000.

Sortida

Per a cada cas, escriviu de més petites a més grans les monedes necessàries per a sumar cc amb el mínim nombre de monedes. Escolliu la combinació que usi monedes de valor més gran en cas d’empat. Si no n’hi ha cap, escriviu “no”.

Observació

Resoleu aquest problema amb programació dinàmica.

Public test cases

  • Input

    6    3  1 2 5
20   4  2 4 6 17
15   4  2 4 6 17
115 11  1 27 49 58 70 72 90 95 97 98 100
1000 3  400 600 1000

    Output

    6 = 1 5
20 = 2 6 6 6
no
115 = 1 1 1 27 27 58
1000 = 1000
    • Information
    Author
    Enric Rodríguez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++