Dues monedes de cada (1)

Donat un nombre $x$ i $n$ valors diferents de monedes $m_1$ … $m_n$ , 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 $m_1$ … $m_n$ . Suposeu $1 \le n \le 20$ , $1 \le m_i \le x \le 1000$ , i que totes les $m_i$ 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' < \dots$ . 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.

Informació del problema

Autoria: Salvador Roura

Generació: 2026-01-25T11:11:52.454Z