Dues monedes de cada (1) P62113


Statement
 

pdf   zip

thehtml

Donat un nombre x i n valors diferents de monedes m1mn, de quantes maneres es pot aconseguir canvi x usant cada valor com a molt dues vegades? Considereu diferents dues monedes amb el mateix valor.

Per exemple, si x = 4 i disposem dels dos valors 1 i 2, llavors tenim tres maneres: 1 + 1′ + 2, 1 + 1′ + 2′, i també 2 + 2′.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb x i n, seguit de m1mn. Suposeu 1 ≤ n ≤ 20, 1 ≤ mix ≤ 1000, i que totes les mi són diferents.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les maneres d’aconseguir exactament canvi x usant cada valor com a molt dues vegades. Escriviu cada solució amb els valors de petit a gran. A l’hora d’ordenar els valors, suposeu 1 < 1′ < 2 < 2′ < …. Useu “1p” per escriure 1′, etcètera. Escriviu una línia amb 10 guions al final de cada cas.

Pista

Un backtracking mitjanament espurgat hauria de ser suficient.

Public test cases
  • Input

    4 2  1 2
    400 1  200
    400 1  300
    5 3  4 2 1
    5 5  1 2 3 4 5
    

    Output

    4 = 1 + 1p + 2
    4 = 1 + 1p + 2p
    4 = 2 + 2p
    ----------
    400 = 200 + 200p
    ----------
    ----------
    5 = 1 + 2 + 2p
    5 = 1 + 4
    5 = 1 + 4p
    5 = 1p + 2 + 2p
    5 = 1p + 4
    5 = 1p + 4p
    ----------
    5 = 1 + 1p + 3
    5 = 1 + 1p + 3p
    5 = 1 + 2 + 2p
    5 = 1 + 4
    5 = 1 + 4p
    5 = 1p + 2 + 2p
    5 = 1p + 4
    5 = 1p + 4p
    5 = 2 + 3
    5 = 2 + 3p
    5 = 2p + 3
    5 = 2p + 3p
    5 = 5
    5 = 5p
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++