Golf me some cash from the ATM

Question

The task is simple. Get me some 1000, 500 and 100 notes.

How ? you might ask. Don't worry, no need of robbing a bank as there is an ATM nearby which accepts your credit card. But your credit limit is just enough for the task so you have to be careful with the withdrawals.

Challenge

Given the number of 1000, 500 and 100 notes required, calculate the specific withdrawals needed to get at least those many notes. In each withdrawal, the ATM can spit out each of the note based on the following rules:

• Amount withdrawn (A) is less than 5000
  • If A%1000 == 0, then ATM spits 1 500 note, 5 100 notes and rest 1000 notes
  • Else if A%500 == 0, the ATM spits 5 100 notes, rest 1000 notes
  • Else if A%1000 < 500, the ATM spits floor(A/1000) 1000 notes and rest 100 notes
  • Else if A%1000 > 500, the ATM spits floor(A/1000) 1000 notes, 1 500 and rest 100 notes
• Amount withdrawn is greater than equal to 5000
  • If A%1000 == 0, then the ATM spits 2 500 notes and rest 1000 notes
  • Else if, A%500 == 0, the ATM spits 1 500 note and rest 1000 notes
  • Else if A%1000 < 500, the ATM spits floor(A/1000) 1000 notes and rest 100 notes
  • Else if A%1000 > 500, the ATM spits floor(A/1000) 1000 notes, 1 500 and rest 100 notes

For clarification, here is a complete table of notes withdrawn for all possible amounts up to 7000 (you can withdraw more, but the pattern does not change afterwards). The order is <1000> <500> <100>:

 100 => 0 0 1                  2500 => 2 0 5                   4800 => 4 1 3
 200 => 0 0 2                  2600 => 2 1 1                   4900 => 4 1 4
 300 => 0 0 3                  2700 => 2 1 2                   5000 => 4 2 0
 400 => 0 0 4                  2800 => 2 1 3                   5100 => 5 0 1
 500 => 0 0 5                  2900 => 2 1 4                   5200 => 5 0 2
 600 => 0 1 1                  3000 => 2 1 5                   5300 => 5 0 3
 700 => 0 1 2                  3100 => 3 0 1                   5400 => 5 0 4
 800 => 0 1 3                  3200 => 3 0 2                   5500 => 5 1 0
 900 => 0 1 4                  3300 => 3 0 3                   5600 => 5 1 1
1000 => 0 1 5                  3400 => 3 0 4                   5700 => 5 1 2
1100 => 1 0 1                  3500 => 3 0 5                   5800 => 5 1 3
1200 => 1 0 2                  3600 => 3 1 1                   5900 => 5 1 4
1300 => 1 0 3                  3700 => 3 1 2                   6000 => 5 2 0
1400 => 1 0 4                  3800 => 3 1 3                   6100 => 6 0 1
1500 => 1 0 5                  3900 => 3 1 4                   6200 => 6 0 2
1600 => 1 1 1                  4000 => 3 1 5                   6300 => 6 0 3
1700 => 1 1 2                  4100 => 4 0 1                   6400 => 6 0 4
1800 => 1 1 3                  4200 => 4 0 2                   6500 => 6 1 0
1900 => 1 1 4                  4300 => 4 0 3                   6600 => 6 1 1
2000 => 1 1 5                  4400 => 4 0 4                   6700 => 6 1 2
2100 => 2 0 1                  4500 => 4 0 5                   6800 => 6 1 3
2200 => 2 0 2                  4600 => 4 1 1                   6900 => 6 1 4
2300 => 2 0 3                  4700 => 4 1 2                   7000 => 6 2 0
2400 => 2 0 4

List provided by Martin

The Catch

Since the credit limit in your credit card is just enough, you need to make sure that the total amount withdrawn across the withdrawals is the minimum possible for the given input/requirement of notes.

Input

Input can be in any favorable format for three numbers corresponding to the number of notes required of value 1000, 500 and 100. Not necessarily in that order.

Output

Output is the amount to be withdrawn in each transaction separated by a new line.

Examples

Input (format <1000> <500> <100>):

3 4 1

Output:

600
600
600
3600

few more:

7 2 5
5000
3500

1 2 3
600
1700

21 14 2
600
600
600
1600
5000
5000
5000
5000
5000

Assumptions

• You may assume that the ATM has infinite number of notes of each amount.
• You may also assume that you can make any number of transactions.
• Furthermore, the solution to some input values might not be unique, so you can output any 1 of the solution which fulfills the minimum amount possible and minimum notes required conditions.

As usual, you may write a full program reading input via STDIN/ARGV and printing output to STDOUT or a function taking input via arguments and returns either a list of integer corresponding to the amounts or a string with amounts separated by a new line.

This is code-golf so shortest code in bytes wins.

Answer 1

JavaScript, 184 148

function g(a,b,c){x=[];while(a>0||b>0||c>0){i=b<3||a<4?a:4;a-=i;if(i>3&&b>1){b-=2;i++}else{i+=(c--<b&&i>4?0:.1)+(b-->0?.5:0)}x.push(i*1e3)}return x}

http://jsfiddle.net/vuyv4r0p/2/

returns a list of integers corresponding to the withdrawal amounts

Answer 2

Perl 5: 223

Edit

This solution was done with a wrong assumption that 7K is the ATM limit. This actually made the task more interesting as it required dynamic programming (the move pattern was quite regular, but hard-coding it would be likely longer than calculating live as I did). With any amount possible the move pattern is so regular that it is trivial to hard-code it. I don't know if the solution by @hoffmale is now correct, but it will be among these lines. So sadly it will be another task where first somebody comes with a solution and then it gets ported to a golfing language for a win.

A bit slower than the original solution (but still sub-second for parameters below 100).

#!perl -pa
$c{0,0}=$f=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/.(?=.$)/>($n=$c{$i-$`,$j-$'})||${$r=\$c{$i,$j}}<($x=$n+$&)&&$$r
or$f=$$r="$x $n".($'.$&+5*$`)."00
"for 204..206,105,106,11..15,110..114}}$_=$f."100
"x($c-$f+3);s/.*\b3//

Faster 259 solution.

#!perl -pa
$c{0,0}=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/\B./<($%=$c{$i-$&,$j-$'}+$`)&&(!${$r=\$c{$i,$j}}||$$r>$%)and$d{$i,$j}=$_,$$r=$%for
qw/024 025 026 015 016/,101..105,110..114}}
$d{$b,$a}=~/\B./,$c-=$`,$b-=$&,$a-=$',print$'.$`+5*$&,"00
"while$a+$b;$_="100
"x$c

Uses STDIN:

$perl atm.pl <<<"21 14 2"
5000
5000
5000
5000
5000
600
600
600
1600