<?php
class Coins {
private $matrix = array(); private $count = 0;
private function compute($n) {
if (!isset($this->matrix[$n])) { if ($n >= 0 && $n < 12) {
$this->matrix[$n] = $n;
} else {
$a = $n >> 1;
$c = $n >> 2;
$this->matrix[$a] = !isset($this->matrix[$a]) ?
$this->compute($a) : $this->matrix[$a]; $this->matrix[$b] = !isset($this->matrix[$b]) ?
$this->compute($b) : $this->matrix[$b]; $this->matrix[$c] = !isset($this->matrix[$c]) ?
$this->compute($c) : $this->matrix[$c]; $this->matrix[$n] = max(($this->matrix[$a] + $this->matrix[$b] + $this->matrix[$c]), $n); }
}
return $this->matrix[$n];
}
public function init() {
for ($i=0; $i<$tests; $i++) {
echo $this->compute($n) . PHP_EOL;
}
}
}
$lps = new Coins();
$lps->init();
?>
PD9waHAKCmNsYXNzIENvaW5zIHsKICAgIHByaXZhdGUgJG1hdHJpeCA9IGFycmF5KCk7CiAgICBwcml2YXRlICRjb3VudCA9IDA7CgogICAgcHJpdmF0ZSBmdW5jdGlvbiBjb21wdXRlKCRuKSB7CiAgICAgIGlmICghaXNzZXQoJHRoaXMtPm1hdHJpeFskbl0pKSB7CiAgICAgICAgJHRoaXMtPmNvdW50Kys7CiAgICAgICAgaWYgKCRuICA+PSAwICYmICRuIDwgMTIpIHsKICAgICAgICAgICAgJHRoaXMtPm1hdHJpeFskbl0gPSAkbjsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAkYSA9ICRuID4+IDE7CiAgICAgICAgICAgICRiID0gZmxvb3IoJG4vMyk7CiAgICAgICAgICAgICRjID0gJG4gPj4gMjsKICAgICAgICAgICAgJHRoaXMtPm1hdHJpeFskYV0gPSAhaXNzZXQoJHRoaXMtPm1hdHJpeFskYV0pID8gJHRoaXMtPmNvbXB1dGUoJGEpIDogJHRoaXMtPm1hdHJpeFskYV07CiAgICAgICAgICAgICR0aGlzLT5tYXRyaXhbJGJdID0gIWlzc2V0KCR0aGlzLT5tYXRyaXhbJGJdKSA/ICR0aGlzLT5jb21wdXRlKCRiKSA6ICR0aGlzLT5tYXRyaXhbJGJdOwogICAgICAgICAgICAkdGhpcy0+bWF0cml4WyRjXSA9ICFpc3NldCgkdGhpcy0+bWF0cml4WyRjXSkgPyAkdGhpcy0+Y29tcHV0ZSgkYykgOiAkdGhpcy0+bWF0cml4WyRjXTsKICAgICAgICAgICAgJHRoaXMtPm1hdHJpeFskbl0gPSBtYXgoKCR0aGlzLT5tYXRyaXhbJGFdICsgJHRoaXMtPm1hdHJpeFskYl0gKyAkdGhpcy0+bWF0cml4WyRjXSksICRuKTsKICAgICAgICB9CiAgICAgIH0KICAgICAgcmV0dXJuICR0aGlzLT5tYXRyaXhbJG5dOwogICAgICAKICAgIH0KCiAgICBwdWJsaWMgZnVuY3Rpb24gaW5pdCgpIHsKICAgICAgICAkdGVzdHMgPSBzdHJlYW1fZ2V0X2xpbmUoU1RESU4sIDEwMDAwMDAwMDAwLCBQSFBfRU9MKTsKICAgICAgICBmb3IgKCRpPTA7ICRpPCR0ZXN0czsgJGkrKykgewogICAgICAgICAgICAkbiA9IHN0cmVhbV9nZXRfbGluZShTVERJTiwgMjAwMDAwMDAwMDAsIFBIUF9FT0wpOwogICAgICAgICAgICBlY2hvICR0aGlzLT5jb21wdXRlKCRuKSAuIFBIUF9FT0w7CiAgICAgICAgCiAgICAgICAgfQogICAgfQp9CgokbHBzID0gbmV3IENvaW5zKCk7CiRscHMtPmluaXQoKTsKPz4=