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)