Tots els canvis P29230

Feu un programa tal que, per a cada natural $n$ donat, escrigui totes les maneres diferents d’obtenir $n$ cèntims d’euro amb el nostre sistema de monedes actual (1 cèntim, 2 cèntims, 5 cèntims, 10 cèntims, 20 cèntims, i 50 cèntims).

Entrada

L’entrada consisteix en una seqüència de naturals $1 \le n \le 50$.

Sortida

Per a cada $n$, escriviu totes les maneres d’obtenir $n$ cèntims, cadascuna en una línia apart. Els nombres de cada línia han d’estar ordenats de gran a petit. Les solucions per a cada $n$ han d’aparèixer en ordre lexicogràfic invers. Deixeu una línia en blanc després de la sortida de cada cas.

Observació

Un programa senzill de tornada enrera que calculi el resultat per a cada $n$ donada (encara que estigui repetida) és prou ràpid per a aquest problema.