High School Programming League Problems Archive

In an effort to keep their customers satisfied, banks always make sure that their ATM-s are properly stocked with banknotes of different face value. Suppose however that for a few hours a careless bank did not supply extra banknotes to one of its ATM-s, while customers were still withdrawing cash from the machine.

The ATM in question initially contains some banknotes with face values of 5Eur, 10Eur, 20Eur, and 50Eur. Each customer can attempt to withdraw an amount of money which is a multiple of 5Eur, but no more than 2000Eur. The ATM dispenses banknotes according to the following rules:

• delivers the sum of money in a way which minimizes the total number of banknotes withdrawn from the ATM in the transaction (if there is more than one such possibility, given the current state of the ATM, the possibility in which the number of withdrawn 50Eur notes is smaller is chosen),
• denies the transaction if the withdrawal is impossible to perform due to a shortage of banknotes, or if the withdrawal would require more than 50 banknotes.

It is your task to determine how many customers are required until withdrawal from the ATM proves impossible, assuming the most pessimistic configuration of withdrawal amounts.

Input

The input consists of four integers from the range 0 through 10000, separated by spaces. They represent the number of banknotes initially available in the ATM, of face values 5Eur, 10Eur, 20Eur, and 50Eur, respectively.

Output

Your program should output a sequence of space-separated integers which are divisible by 5 and belong to the range 5 through 2000. They denote the amounts of cash to be withdrawn by successive customers of the ATM. The sequence should consist of no more than 100000 numbers.

Score

The testing system will simulate the operation of the described ATM and will determine if the provided sequence contains a withdrawal attempt which cannot be performed according to the problem rules. If so, the number of points awarded to the solution will be inversely proportional to the number of integers in the output sequence (1 point for the shortest possible sequence, proportionally less for longer sequences). If the answer is found to be incorrect, the test will be considered failed and the solution will receive 0 points for it.

All programs will be run for 10 different sets of input data, and the sum of scores obtained in individual tests will be the final score of the program.

Example 1

Input:
2 2 2 100

Output:
45 30

Score:
1 point

In the above example the ATM will dispense to the first customer 2 banknotes of 20Eur face value and one note of 5Eur face value. The withdrawal attempted by the second customer proves impossible due to a shortage of change. The solution is awarded 1 point since the printed sequence is the shortest possible. There also exist other solutions having the same sequence length, eg. "90 135"; any such solution will also be awarded 1 point.

Example 2

Input:
9 0 4 10000

Output:
5 5 5 5 5 5 5 5 5 5

Score:
0.2 points

In this example the solution withdraws successive banknotes of 5Eur face value from the ATM, one-by-one, until the supply of 5Eur notes is depleted. However, for the input data, the optimal solution consists of only two customers, the first withdrawing 85Eur from the ATM (delivered in the form of 4 banknotes of 20Eur face value and one 5Eur banknote), whereas the second customer makes an attempt to withdraw 45Eur which does not succeed due to a shortage of change.

Example 3

Input:
9 0 4 10000

Output:
45 85

Score:
0 points (wrong answer)

The input data is the same as in Example 2. The provided solution is incorrect since both the withdrawals can in fact be performed: the first customer will receive 2 banknotes of 20Eur face value and one 5 Eur banknote, whereas the second - one 50Eur banknote, one 20Eur banknote, and 3 banknotes of 5Eur face value. As you have probably noticed by now the order of withdrawals is relevant; in the previous example we showed that the sequence 85 45 contains a failed withdrawal attempt.