Kolika způsoby lze mincemi zaplatit částku

Vstup:

k = počet druhů mincí (\le 200), následuje k řádek, na každé hodnota jednoho z druhu mincí, tedy

a_1

\vdots

a_k

n = částka (\le 10 000)

Ukázka:

2
1
2
50

výstup 26

3
5
2
1
145

výstup 1110

Výstup:

číslo (až 4\text{e}9, tedy potřeba unsigned long), počet způsobů jak zaplatit částku n, každého druhu mince máme neomezeně

Důležité: Nehledí se na pořadí mincí, tj. 1,2 a 2,1 je 1 způsob zaplacení.

Proto u 1. vstupu taky 26:

1, \dots, 1

a pak 25 možností, které se liší počtem dvojek

1, 2, 1, \dots, 1 (jedna dvojka)

1,2,2, 1, \dots, 1

\vdots

2, \dots , 2 (25 dvojek)