fork download
copy 
  1. <?php
  2. check(120, [10, 60, 100]);
  3. check(740, [10, 50, 100, 500, 1000]);
  4.  
  5. function check($target, $notes) {
  6.  
  7. 	$inf = 999999;
  8. 	$counts = [0 => 0];
  9.  
  10. 	foreach (range(1, $target) as $n) {
  11. 		$counts[$n] = $inf;
  12. 		foreach ($notes as $note) {
  13. 			if ($n >= $note) {
  14. 				$cur_count = $counts[$n-$note] + 1;
  15. 				if ($cur_count < $counts[$n]) {
  16. 					$counts[$n] = $cur_count;
  17. 				}
  18. 			}
  19. 		}
  20. 	}
  21.  
  22. 	if ($counts[$target] == $inf) {
  23. 		echo "impossible\r\n";
  24. 		return;
  25. 	}
  26.  
  27. 	$result = [];
  28. 	while ($target > 0) {
  29. 		foreach ($notes as $note) {
  30. 			if ($counts[$target-$note] == $counts[$target]-1) {
  31. 				$result[] = $note;
  32. 				$target -= $note;
  33. 				break;
  34. 			}
  35. 		}
  36. 	}
  37. 	echo implode(', ', $result), "\r\n";
  38. }
Success #stdin #stdout 0.02s 24640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
60, 60
10, 10, 10, 10, 100, 100, 500
https://ideone.com/cO6Pdf
language:
PHP (php 7.3.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!