Ideone.com

download

copy

<?php
 
error_reporting(-1);
 
$amount = 740;
 
$bills = array(
	10 => 10,
	50 => 10,
	100 => 10,
	500 => 10,
);
 
$keysBills = array_keys($bills);
 
$attempts = 0;
 
function countBillsSum($billsCopy) {
 
	$valuesBillsCopy = array_values($billsCopy);
	$keysBillsCopy = array_keys($billsCopy);
 
	for($i = 0; $i < count($billsCopy); $i++) {
		$result[$i] = $valuesBillsCopy[$i] * $keysBillsCopy[$i];
	}	
	$result = array_sum($result);
	return $result;	
}	
 
function findChange($amount, $keysBills, $bills, $billNumber) {
 
	echo "start $billNumber";
 
	global $attempts;
 
	$currentBill = $keysBills[$billNumber];
 
	$currentMaxBills = min(floor($amount / $keysBills[$billNumber]), $bills[$currentBill]);
 
	for ($i = $currentMaxBills; $i >= 0; $i--) {
 
		echo "$i\n";
 
		$attempts++;
		$billsCopy = $bills;
		$billsCopy[$currentBill] = $i;
 
		if ($billNumber > 0) { 
			findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
		} elseif (countBillsSum($billsCopy) == $amount) {
			echo implode(", ", array_values($billsCopy))."\n";
			break;
		} 
	}
	echo "end\n";
	return;
}
 
echo findChange($amount, $keysBills, $bills, 3);
 
//echo selectMinimumBillsArray(findChange($amount, $keysBills, $bills, 0, array()));
 
echo "\n".$attempts;

Success #stdin #stdout 0.03s 20568KB

stdin

copy

Standard input is empty

stdout

copy

start 31
start 27
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
6
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
5
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
4
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
3
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
2
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
4, 0, 2, 1
end
end
1
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
4, 2, 1, 1
end
1
start 010
9
9, 1, 1, 1
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
0
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
4, 4, 0, 1
end
3
start 010
9
9, 3, 0, 1
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
end
0
start 27
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
4, 0, 7, 0
end
end
6
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
4, 2, 6, 0
end
1
start 010
9
9, 1, 6, 0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
5
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
4, 4, 5, 0
end
3
start 010
9
9, 3, 5, 0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
4
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
4, 6, 4, 0
end
5
start 010
9
9, 5, 4, 0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
3
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
4, 8, 3, 0
end
7
start 010
9
9, 7, 3, 0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
2
start 110
start 010
9
8
7
6
5
4
4, 10, 2, 0
end
9
start 010
9
9, 9, 2, 0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
1
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
0
start 110
start 010
9
8
7
6
5
4
3
2
1
0
end
9
start 010
9
8
7
6
5
4
3
2
1
0
end
8
start 010
9
8
7
6
5
4
3
2
1
0
end
7
start 010
9
8
7
6
5
4
3
2
1
0
end
6
start 010
9
8
7
6
5
4
3
2
1
0
end
5
start 010
9
8
7
6
5
4
3
2
1
0
end
4
start 010
9
8
7
6
5
4
3
2
1
0
end
3
start 010
9
8
7
6
5
4
3
2
1
0
end
2
start 010
9
8
7
6
5
4
3
2
1
0
end
1
start 010
9
8
7
6
5
4
3
2
1
0
end
0
start 010
9
8
7
6
5
4
3
2
1
0
end
end
end
end

2031

Discover > Sphere Engine API

Discover > IDE Widget

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language