fork(1) download
  1. <?php
  2.  
  3. class Coins {
  4. private $matrix = array();
  5. private $count = 0;
  6.  
  7. private function compute($n) {
  8. if (!isset($this->matrix[$n])) {
  9. $this->count++;
  10. if ($n >= 0 && $n < 12) {
  11. $this->matrix[$n] = $n;
  12. } else {
  13. $a = $n >> 1;
  14. $b = floor($n/3);
  15. $c = $n >> 2;
  16. $this->matrix[$a] = !isset($this->matrix[$a]) ? $this->compute($a) : $this->matrix[$a];
  17. $this->matrix[$b] = !isset($this->matrix[$b]) ? $this->compute($b) : $this->matrix[$b];
  18. $this->matrix[$c] = !isset($this->matrix[$c]) ? $this->compute($c) : $this->matrix[$c];
  19. $this->matrix[$n] = max(($this->matrix[$a] + $this->matrix[$b] + $this->matrix[$c]), $n);
  20. }
  21. }
  22. return $this->matrix[$n];
  23.  
  24. }
  25.  
  26. public function init() {
  27. $tests = stream_get_line(STDIN, 10000000000, PHP_EOL);
  28. for ($i=0; $i<$tests; $i++) {
  29. $n = stream_get_line(STDIN, 20000000000, PHP_EOL);
  30. echo $this->compute($n) . PHP_EOL;
  31.  
  32. }
  33. }
  34. }
  35.  
  36. $lps = new Coins();
  37. $lps->init();
  38. ?>
Success #stdin #stdout 0s 82560KB
stdin
Standard input is empty
stdout
Standard output is empty