Olympiad hobby. Coin exchange

Hey. Today is Monday, so I decided that I should start my work day with warming up my fingers and brain. For those who do not know: my olympiad hobby is solving olympiad programming problems that I take from the site http://uva.onlinejudge.org/ . Today we have to solve the problem of the exchange of coins from the field of dynamic programming. The task is not very difficult, but there is something to think about, so I ask those interested in under the cat. By the way, this is our third task, but, of course, the most interesting of all.

A small lyrical digression.

My programmer's journey began far from 3 years, when many future programmers already dismantled the calculator and made a computer out of it. I started programming at school in grade 8. By the way, my school was far from a technical direction, so in my endeavors I was almost alone. But, thanks to the director of our school, we had a programming circle where we were preparing for the school programming contest. There were no more than three people there at one time, but fortunately our teacher did not upset us. My teacher of programming was Kavokin AA, in part because of him I embarked on such an amazing way for a programmer. So, each lesson, our mentor began with a logical task, so that we would stir up our convolutions. I liked it so much at school that I decided to torture you too, so today we will start with a small logical task that will help us to warm up.

Logical task to warm up:

In our city, travel by public transport is paid directly during the trip, for which the conductor runs the bus, collecting the fare from everyone. Ticket price is 20 rubles. Once, at one of the stops, 5 people entered the bus. One of them silently paid the conductor 100 rubles, and the latter, without asking any questions, counted out 5 tickets and gave them to the one who paid. Question: how did the conductor realize that the payment was made immediately for all five, provided that nothing indicated that they were all together?

I will allow you to leave the task unanswered because I am confident in your ingenuity And as soon as the correct answer appears in the comments, I immediately bring the link here.
UPD: The answer is found in the comments of the user ogra
')

Condition

I hope the task that I threw you to warm up, will successfully affect your brain activity. Now we are finally going to solve the Olympiad problem. Our today's task is the task of coin exchange .

A brief translation of the problem statement

After purchasing in a large department store, Mel got the change in the amount of 17 cents. He received one ten-cent coin, one five-cent coin and 2 coins of 1 cent each. Later that day, he was shopping in a mini market, where he also received change in the amount of 17 cents. This time he received two coins of 5 cents and 7 coins of 1 cent. Then Mel wondered: "How many shops can I visit and get a change of 17 cents with a different set of coins?" After a little brainstorming, he determined answer 6. Then he challenged you to solve a more general case.

Write a program that will determine the number of different combinations of American coins (1 cent, 5 cents, 10 cents, 25 and 50 cents) that can add up to a certain amount.

Input : The input will consist of a set of numbers between 0 and 30000 inclusive, one per line.

Output : for each input number, you need to determine the number of combinations and output, as shown in the example.

Example:
Input:
17
eleven
four

Output:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.

As usual, I recommend you to try to solve the problem yourself. And as soon as you decide, come back to us and show off your results.

So let's get started ...

Decision

The task is clearly from the field of dynamic programming, and such problems are usually solved with the help of recursive dependencies. We need to determine what kind of recursive dependence in our case.

You can immediately notice that the number of combinations does not differ when passing from 1 cents to 4 - this is 1 option, when passing from 5 cents to 9 - these are 2 options, when passing from 10 cents to 14 - these are 4 options, etc. This happens because inside such a “five” one 1 cent coin cannot be replaced with anything. Thus, we determined that solving the problem for each number is meaningless, so we will solve it for each “five”.

You can also notice that the combinations for each next "five" accurately repeat the combinations of the previous "five" (with the addition of the necessary number of 1 cent coins to the end of the combination) and a certain number of new combinations. It becomes clear that the number of combinations of the next “five” is dependent on the number of combinations of the previous “fives”. We will draw a table where the columns will be “fives”, and the rows will look at the types of coins, and at the cut-off, it will be determined how many new combinations gave rise to the type of coins (in combination with all the smaller ones) at a specific step - the “five”:

	one	five	ten	15	20	25	thirty	35	40	45	50	55
one	one	0	0	0	0	0	0	0	0	0	0	0
five	0	one	one	one	one	one	one	one	one	one	one	one
ten	0	0	one	one	2	2	3	3	four	four	five	five
25	0	0	0	0	0	one	one	2	2	3	four	five
50	0	0	0	0	0	0	0	0	0	0	one	one
Σ	one	2	four	6	9	13	18	24	31	39	50	62

The last line displays the number of combinations on this "five"
For example: at step 35 (8 five: 35-39)
having only 1 cent coin, no new combinations appear,
from coins 1 cent and 5 cents, you can invent 1 new combination: 5 + 5 + 5 + 5 + 5 + 5 + 5 + 1 (from 0 to 4)
1 cent, 5 cents, 10 cents - 10 combinations: 10 + 10 + 10 + 5 + 1 (from 0 to 4), 10 + 10 + 5 + 5 + 5 + 1, 10 + 5 * 5 + 1
1, 5, 10, 25 - 2 new combinations: 25 + 10 + 1, 25 + 5 + 5 + 1

The number of new combinations in each step of coins 1 cent and 5 cents equals 1, because this combination is generated by the addition of a 5 cent coin to the previous combination. Those. for the second five 5 + 1, then 5 + 5 + 1, then 5 + 5 + 5 + 1, etc., 1 new combination at each step.
Also in this table, it is not difficult to see a recursive relationship: the number of new combinations in step i composed of coins 1-10 equals the number of new combinations of coins 1-5 in step i-1 plus the number of new combinations of coins 1-10 in step i- 2 (when we had 1 dimetr less in our possession). Similarly, for a 25 cent coin and a 50 cent coin.

As a result, we have 2 formulas and 3 recursive dependencies:
N (1, i) = 0, except N (1, 0) = 1
N (5, i) = 1
N (10, i) = N (5, i-1) + N (10, i-2)
N (25, i) = N (10, i-3) + N (25, i-5)
N (50, i) = N (25, i-5) + N (50, i-10)
S (i) = S (i-1) + N (1, i) + N (5, i) + N (10, i) + N (25, i) + N (50, i)
Where N is the matrix defined above, and S is the desired number of combinations.

Now we can only calculate the required number of steps from the beginning to the requested "five", counting at each step the total number of combinations (S). Given the fact that there will be a lot of tests in the problem, it is possible to use for the new tests a previously calculated piece of the matrix and only supplement its missing part. It is also very important to understand that with the maximum amount specified by the condition of the problem: 30000 cents, the total number of combinations will exceed int and even long, therefore I recommend using 8 byte unsigned variables to count the number of combinations.

I believe that there is a more elegant solution than the one proposed above, but I don’t see it yet, so I’m waiting for interesting algorithms from you. My solution in C ++ can be downloaded here . You can check the correctness of your decision here (registration is required). Good luck, gentlemen!

Accepted (0.024)