P1474 [USACO2.3] Money System / [USACO07OCT] Cow Cash G

The cows have not only created their own political party but also chosen to establish their own currency system. Because of their unique way of thinking, they are curious about monetary values. Traditionally, a currency system consists of denominations $1,5,10,20,25,50,100$. The cows want to know how many different ways there are to form a specified value using the coins in the currency system. For example, using a currency system with denominations $1,2,5,10$ to make a value of $18$, some possible ways are: $18 \times 1$, $9 \times 2$, $8 \times 2+2 \times 1$, $3 \times 5+2+1$, and so on. Write a program to compute how many ways there are to make a given amount using the provided currency system. It is guaranteed that the total fits in a $64$-bit signed integer.

The first line contains two integers, the number of coin types $V$ ($1 \leq V \leq 25$) and the target value $N$ ($1 \leq N \leq 10,000$). The second line contains $V$ integers, the denominations of all coins.

A single line with one integer, the number of ways.

Translated from NOCOW. USACO Training Section 2.3. Translated by ChatGPT 5