<?php
check(120, [10, 60, 100]);
check(740, [10, 50, 100, 500, 1000]);
function check($target, $notes) {
$inf = 999999;
$counts = [0 => 0];
foreach (range(1, $target) as $n) { $counts[$n] = $inf;
foreach ($notes as $note) {
if ($n >= $note) {
$cur_count = $counts[$n-$note] + 1;
if ($cur_count < $counts[$n]) {
$counts[$n] = $cur_count;
}
}
}
}
if ($counts[$target] == $inf) {
echo "impossible\r\n";
return;
}
$result = [];
while ($target > 0) {
foreach ($notes as $note) {
if ($counts[$target-$note] == $counts[$target]-1) {
$result[] = $note;
$target -= $note;
break;
}
}
}
echo implode(', ', $result), "\r\n"; }
PD9waHAKY2hlY2soMTIwLCBbMTAsIDYwLCAxMDBdKTsKY2hlY2soNzQwLCBbMTAsIDUwLCAxMDAsIDUwMCwgMTAwMF0pOwoKZnVuY3Rpb24gY2hlY2soJHRhcmdldCwgJG5vdGVzKSB7CgoJJGluZiA9IDk5OTk5OTsKCSRjb3VudHMgPSBbMCA9PiAwXTsKCglmb3JlYWNoIChyYW5nZSgxLCAkdGFyZ2V0KSBhcyAkbikgewoJCSRjb3VudHNbJG5dID0gJGluZjsKCQlmb3JlYWNoICgkbm90ZXMgYXMgJG5vdGUpIHsKCQkJaWYgKCRuID49ICRub3RlKSB7CgkJCQkkY3VyX2NvdW50ID0gJGNvdW50c1skbi0kbm90ZV0gKyAxOwoJCQkJaWYgKCRjdXJfY291bnQgPCAkY291bnRzWyRuXSkgewoJCQkJCSRjb3VudHNbJG5dID0gJGN1cl9jb3VudDsKCQkJCX0KCQkJfQoJCX0KCX0KCglpZiAoJGNvdW50c1skdGFyZ2V0XSA9PSAkaW5mKSB7CgkJZWNobyAiaW1wb3NzaWJsZVxyXG4iOwoJCXJldHVybjsKCX0KCgkkcmVzdWx0ID0gW107Cgl3aGlsZSAoJHRhcmdldCA+IDApIHsKCQlmb3JlYWNoICgkbm90ZXMgYXMgJG5vdGUpIHsKCQkJaWYgKCRjb3VudHNbJHRhcmdldC0kbm90ZV0gPT0gJGNvdW50c1skdGFyZ2V0XS0xKSB7CgkJCQkkcmVzdWx0W10gPSAkbm90ZTsKCQkJCSR0YXJnZXQgLT0gJG5vdGU7CgkJCQlicmVhazsKCQkJfQoJCX0KCX0KCWVjaG8gaW1wbG9kZSgnLCAnLCAkcmVzdWx0KSwgIlxyXG4iOwp9