2000 LSU Computer Science High School Programming Contest
Problem 4: Making Change (Judge Copy)

• Problem Statement
• Test Data 0
• Output for Test Data 0
• Test Data 1
• Output for Test Data 1
• Test Data 2
• Output for Test Data 2
• Test Data 3
• Output for Test Data 3

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Problem 4: Making Change (Judge Copy)

Given an amount of money and unlimited (almost) numbers of coins we know that an amount of money may be made up in a variety of ways. A more interesting problem arises when goods are bought and need to be paid for, with the possibility that change may need to be given. Given the finite resources of most wallets nowadays, we are constrained in the number of ways in which we can make up an amount to pay for our purchases--assuming that we can make up the amount in the first place, but that is another story.

The problem we will be concerned with will be to minimize the number of coins that change hands at such a transaction, given that the shopkeeper has an adequate supply of all coins. (The set of coins will consist of 5c, 10c, 20c, 50c, $1 and $2.) Thus if we need to pay 55c, and we do not hold a 50c coin, we could pay this as 2*20c + 10c + 5c to make a total of 4 coins. If we pay with a $1 coin, we will receive 45c in change which also involves 4 coins (one $1 coin, 2 20c coins, and a 5c coin). But if we were to pay $1.05 (a $1 coin and a 5c coin), we get 50c change and the total number of coins that changes hands is only 3.

Write a program that will read in the resources available to you and the amount of the purchase and will determine the minimum number of coins that change hands.

Input

Input will consist of a series of lines, each pair of lines defining a new situation. The first line of a pair line consist of 6 integers representing the numbers of coins available to you in the order given above. The second line of the pair will be a real number representing the value of the transaction, which will always be less than $5.00. The input will be terminated by six zeroes (0 0 0 0 0 0) as the first line of a pair (there will NOT be a second line for this case). The total value of the coins will always be sufficient to make up the amount and the amount will always be achievable, that is it will always be a multiple of 5c.

Output

Output will consist of a series of lines, one for each situation defined in the input. Each line will consist of the minimum number of coins that change hands.

Sample input

2 4 2 2 1 0  
0.95
2 4 2 0 1 0  
0.45
0 0 0 0 0 0

Sample output

2
3

Explanation

0.95 can be made with two coins by you paying with a $1 coin and getting a 5c coin back.

0.55 can be made with three coins by you paying with a $1 coin and getting a 50c and a 5c coin back. This cannot be done in two coins because you do not ahve a 50c coin in your pocket.

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 0

1 0 0 0 0 0
0.05
2 4 2 2 1 0  
0.95
2 4 2 0 1 0  
0.55
0 0 0 0 0 0

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 0

  1
  2
  3

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 1

2 4 2 2 1 0  
0.95
4 2 3 2 1 2
0.75
2 1 3 0 0 1
0.55
0 0 0 0 0 0

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 1

  2
  3
  4

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 2

3 3 3 3 3 3
4.65
1 1 1 1 1 1
2
3 3 3 1 2 2
5.00
2 2 2 1 3 1
4.95
0 0 0 0 0 0

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 2

  5
  1
  3
  5

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 3

5 4 5 0 1 1
0.55
5 4 3 0 0 1
0.55
5 4 3 2 2 3
3.75
1 1 1 1 1 1
0.0
0 0 0 0 0 0

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 3

  3
  4
  4
  0

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.