<?php
list($numberOfGems, $firstJump, $maxIsland, $islandToGemCount) = readInput();
$dag = createDAG($firstJump, $maxIsland);
$sortedVerts = topologicalSort($dag);
echo getMaxDistance($sortedVerts, $firstJump, $islandToGemCount, $numberOfGems, $dag);
function getMaxDistance($sortedVerts, $firstJump, $islandToGemCount, $numberOfGems, $dag) {
$dist = array();
$maxDist = $dist[$firstJump] = weight($firstJump, $islandToGemCount);
foreach ($sortedVerts as $u) {
if (!isset($dist[$u]))
$dist[$u] = -1;
$adj = array_keys($dag[$u]);
foreach ($adj as $v) {
if (!isset($dist[$v]))
$dist[$v] = -1;
if ($dist[$v] < ($dist[$u] + weight($v, $islandToGemCount))) {
$dist[$v] = $dist[$u] + weight($v, $islandToGemCount);
if ($dist[$v] > $maxDist) {
$maxDist = $dist[$v];
if ($maxDist >= $numberOfGems) {
break;
}
}
}
}
if ($maxDist >= $numberOfGems) {
break;
}
}
return $maxDist;
}
function readInput() {
$row = explode(" ", trim(fgets(STDIN)));
$numberOfGems = $row[0];
$firstJump = $row[1];
$maxIsland = 0;
$islandToGemCount = array();
for ($i = 0; $i < $numberOfGems; $i++) {
$curr_p = trim(fgets(STDIN));
if ($curr_p > $maxIsland)
$maxIsland = $curr_p;
if (!isset($islandToGemCount[$curr_p]))
$islandToGemCount[$curr_p] = 0;
$islandToGemCount[$curr_p] += 1;
}
return array($numberOfGems, $firstJump, $maxIsland, $islandToGemCount);
}
function createDAG($firstJump, $maxIsland) {
$dag = array();
addEdges($firstJump, $firstJump, $maxIsland, $dag);
return $dag;
}
function weight($v, $islandToGemCount) {
return (isset($islandToGemCount[$v]) ? $islandToGemCount[$v] : 0);
}
function addEdges($vert, $jump, $maxIsland, &$dag) {
if ($jump <= 0)
return;
if (!isset($dag[$vert])) {
$dag[$vert] = array();
}
$init = $jump - 1;
for ($i = $init; $i <= $init + 2; $i++) {
$newVert = $vert + $i;
if (($newVert > 0) && ($newVert <= $maxIsland) && ($newVert != $vert) && (!isset($dag[$vert][$newVert]))) {
//echo "adding edge $vert to $newVert\n";
$dag[$vert][$newVert] = 1;
addEdges($newVert, $i, $maxIsland, $dag);
}
}
}
function topologicalSort($dag) {
$visited = array();
$queue = array();
foreach ($dag as $vert => $data) {
if (!isset($visited[$vert])) {
visit($dag, $vert, $visited, $queue);
}
}
$stack = array_reverse($queue);
return $stack;
}
function visit($dag, $vert, &$visited, &$queue) {
$visited[$vert] = true;
$adj_list = array_keys($dag[$vert]);
foreach ($adj_list as $adj) {
if (!isset($visited[$adj])) {
visit($dag, $adj, $visited, $queue);
}
}
$queue[] = $vert;
}
?>
PD9waHAKCmxpc3QoJG51bWJlck9mR2VtcywgJGZpcnN0SnVtcCwgJG1heElzbGFuZCwgJGlzbGFuZFRvR2VtQ291bnQpID0gcmVhZElucHV0KCk7CiRkYWcgPSBjcmVhdGVEQUcoJGZpcnN0SnVtcCwgJG1heElzbGFuZCk7CiRzb3J0ZWRWZXJ0cyA9IHRvcG9sb2dpY2FsU29ydCgkZGFnKTsKZWNobyBnZXRNYXhEaXN0YW5jZSgkc29ydGVkVmVydHMsICRmaXJzdEp1bXAsICRpc2xhbmRUb0dlbUNvdW50LCAkbnVtYmVyT2ZHZW1zLCAkZGFnKTsKCmZ1bmN0aW9uIGdldE1heERpc3RhbmNlKCRzb3J0ZWRWZXJ0cywgJGZpcnN0SnVtcCwgJGlzbGFuZFRvR2VtQ291bnQsICRudW1iZXJPZkdlbXMsICRkYWcpIHsKCSRkaXN0ID0gYXJyYXkoKTsKCSRtYXhEaXN0ID0gJGRpc3RbJGZpcnN0SnVtcF0gPSB3ZWlnaHQoJGZpcnN0SnVtcCwgJGlzbGFuZFRvR2VtQ291bnQpOwoJZm9yZWFjaCAoJHNvcnRlZFZlcnRzIGFzICR1KSB7CgkJaWYgKCFpc3NldCgkZGlzdFskdV0pKQoJCQkkZGlzdFskdV0gPSAtMTsKCQkkYWRqID0gYXJyYXlfa2V5cygkZGFnWyR1XSk7CgkJZm9yZWFjaCAoJGFkaiBhcyAkdikgewoJCQlpZiAoIWlzc2V0KCRkaXN0WyR2XSkpCgkJCQkkZGlzdFskdl0gPSAtMTsKCQkJaWYgKCRkaXN0WyR2XSA8ICgkZGlzdFskdV0gKyB3ZWlnaHQoJHYsICRpc2xhbmRUb0dlbUNvdW50KSkpIHsKCQkJCSRkaXN0WyR2XSA9ICRkaXN0WyR1XSArIHdlaWdodCgkdiwgJGlzbGFuZFRvR2VtQ291bnQpOwoJCQkJaWYgKCRkaXN0WyR2XSA+ICRtYXhEaXN0KSB7CgkJCQkJJG1heERpc3QgPSAkZGlzdFskdl07CgkJCQkJaWYgKCRtYXhEaXN0ID49ICRudW1iZXJPZkdlbXMpIHsKCQkJCQkJYnJlYWs7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoKCQlpZiAoJG1heERpc3QgPj0gJG51bWJlck9mR2VtcykgewoJCQlicmVhazsKCQl9Cgl9CglyZXR1cm4gJG1heERpc3Q7Cn0KCmZ1bmN0aW9uIHJlYWRJbnB1dCgpIHsKCSRyb3cgPSBleHBsb2RlKCIgIiwgdHJpbShmZ2V0cyhTVERJTikpKTsKCSRudW1iZXJPZkdlbXMgPSAkcm93WzBdOwoJJGZpcnN0SnVtcCA9ICRyb3dbMV07CgkkbWF4SXNsYW5kID0gMDsKCSRpc2xhbmRUb0dlbUNvdW50ID0gYXJyYXkoKTsKCWZvciAoJGkgPSAwOyAkaSA8ICRudW1iZXJPZkdlbXM7ICRpKyspIHsKCQkkY3Vycl9wID0gdHJpbShmZ2V0cyhTVERJTikpOwoJCWlmICgkY3Vycl9wID4gJG1heElzbGFuZCkKCQkJJG1heElzbGFuZCA9ICRjdXJyX3A7CgkJaWYgKCFpc3NldCgkaXNsYW5kVG9HZW1Db3VudFskY3Vycl9wXSkpCgkJCSRpc2xhbmRUb0dlbUNvdW50WyRjdXJyX3BdID0gMDsKCQkkaXNsYW5kVG9HZW1Db3VudFskY3Vycl9wXSArPSAxOwoJfQoJcmV0dXJuIGFycmF5KCRudW1iZXJPZkdlbXMsICRmaXJzdEp1bXAsICRtYXhJc2xhbmQsICRpc2xhbmRUb0dlbUNvdW50KTsKfQoKZnVuY3Rpb24gY3JlYXRlREFHKCRmaXJzdEp1bXAsICRtYXhJc2xhbmQpIHsKCSRkYWcgPSBhcnJheSgpOwoJYWRkRWRnZXMoJGZpcnN0SnVtcCwgJGZpcnN0SnVtcCwgJG1heElzbGFuZCwgJGRhZyk7CglyZXR1cm4gJGRhZzsKfQoKZnVuY3Rpb24gd2VpZ2h0KCR2LCAkaXNsYW5kVG9HZW1Db3VudCkgewoJcmV0dXJuIChpc3NldCgkaXNsYW5kVG9HZW1Db3VudFskdl0pID8gJGlzbGFuZFRvR2VtQ291bnRbJHZdIDogMCk7Cn0KCmZ1bmN0aW9uIGFkZEVkZ2VzKCR2ZXJ0LCAkanVtcCwgJG1heElzbGFuZCwgJiRkYWcpIHsKCWlmICgkanVtcCA8PSAwKQoJCXJldHVybjsKCWlmICghaXNzZXQoJGRhZ1skdmVydF0pKSB7CgkJJGRhZ1skdmVydF0gPSBhcnJheSgpOwoJfQoJJGluaXQgPSAkanVtcCAtIDE7Cglmb3IgKCRpID0gJGluaXQ7ICRpIDw9ICRpbml0ICsgMjsgJGkrKykgewoJCSRuZXdWZXJ0ID0gJHZlcnQgKyAkaTsKCQlpZiAoKCRuZXdWZXJ0ID4gMCkgJiYgKCRuZXdWZXJ0IDw9ICRtYXhJc2xhbmQpICYmICgkbmV3VmVydCAhPSAkdmVydCkgJiYgKCFpc3NldCgkZGFnWyR2ZXJ0XVskbmV3VmVydF0pKSkgewoJCQkvL2VjaG8gImFkZGluZyBlZGdlICR2ZXJ0IHRvICRuZXdWZXJ0XG4iOwoJCQkkZGFnWyR2ZXJ0XVskbmV3VmVydF0gPSAxOwoJCQlhZGRFZGdlcygkbmV3VmVydCwgJGksICRtYXhJc2xhbmQsICRkYWcpOwoJCX0KCX0KfQoKZnVuY3Rpb24gdG9wb2xvZ2ljYWxTb3J0KCRkYWcpIHsKCSR2aXNpdGVkID0gYXJyYXkoKTsKCSRxdWV1ZSA9IGFycmF5KCk7Cglmb3JlYWNoICgkZGFnIGFzICR2ZXJ0ID0+ICRkYXRhKSB7CgkJaWYgKCFpc3NldCgkdmlzaXRlZFskdmVydF0pKSB7CgkJCXZpc2l0KCRkYWcsICR2ZXJ0LCAkdmlzaXRlZCwgJHF1ZXVlKTsKCQl9Cgl9Cgkkc3RhY2sgPSBhcnJheV9yZXZlcnNlKCRxdWV1ZSk7CglyZXR1cm4gJHN0YWNrOwp9CgpmdW5jdGlvbiB2aXNpdCgkZGFnLCAkdmVydCwgJiR2aXNpdGVkLCAmJHF1ZXVlKSB7CgkkdmlzaXRlZFskdmVydF0gPSB0cnVlOwoJJGFkal9saXN0ID0gYXJyYXlfa2V5cygkZGFnWyR2ZXJ0XSk7Cglmb3JlYWNoICgkYWRqX2xpc3QgYXMgJGFkaikgewoJCWlmICghaXNzZXQoJHZpc2l0ZWRbJGFkal0pKSB7CgkJCXZpc2l0KCRkYWcsICRhZGosICR2aXNpdGVkLCAkcXVldWUpOwoJCX0KCX0KCSRxdWV1ZVtdID0gJHZlcnQ7Cn0KCj8+
Main.java:1: error: class, interface, or enum expected
<?php
^
Main.java:1: error: class, interface, or enum expected
<?php
^
Main.java:1: error: class, interface, or enum expected
<?php
^
Main.java:4: error: class, interface, or enum expected
$dag = createDAG($firstJump, $maxIsland);
^
Main.java:5: error: class, interface, or enum expected
$sortedVerts = topologicalSort($dag);
^
Main.java:6: error: class, interface, or enum expected
echo getMaxDistance($sortedVerts, $firstJump, $islandToGemCount, $numberOfGems, $dag);
^
Main.java:8: error: class, interface, or enum expected
function getMaxDistance($sortedVerts, $firstJump, $islandToGemCount, $numberOfGems, $dag) {
^
Main.java:10: error: class, interface, or enum expected
$maxDist = $dist[$firstJump] = weight($firstJump, $islandToGemCount);
^
Main.java:11: error: class, interface, or enum expected
foreach ($sortedVerts as $u) {
^
Main.java:14: error: class, interface, or enum expected
$adj = array_keys($dag[$u]);
^
Main.java:15: error: class, interface, or enum expected
foreach ($adj as $v) {
^
Main.java:18: error: class, interface, or enum expected
if ($dist[$v] < ($dist[$u] + weight($v, $islandToGemCount))) {
^
Main.java:20: error: class, interface, or enum expected
if ($dist[$v] > $maxDist) {
^
Main.java:22: error: class, interface, or enum expected
if ($maxDist >= $numberOfGems) {
^
Main.java:24: error: class, interface, or enum expected
}
^
Main.java:31: error: class, interface, or enum expected
}
^
Main.java:34: error: class, interface, or enum expected
}
^
Main.java:38: error: class, interface, or enum expected
$numberOfGems = $row[0];
^
Main.java:39: error: class, interface, or enum expected
$firstJump = $row[1];
^
Main.java:40: error: class, interface, or enum expected
$maxIsland = 0;
^
Main.java:41: error: class, interface, or enum expected
$islandToGemCount = array();
^
Main.java:42: error: class, interface, or enum expected
for ($i = 0; $i < $numberOfGems; $i++) {
^
Main.java:42: error: class, interface, or enum expected
for ($i = 0; $i < $numberOfGems; $i++) {
^
Main.java:42: error: class, interface, or enum expected
for ($i = 0; $i < $numberOfGems; $i++) {
^
Main.java:44: error: class, interface, or enum expected
if ($curr_p > $maxIsland)
^
Main.java:46: error: class, interface, or enum expected
if (!isset($islandToGemCount[$curr_p]))
^
Main.java:48: error: class, interface, or enum expected
$islandToGemCount[$curr_p] += 1;
^
Main.java:49: error: class, interface, or enum expected
}
^
Main.java:51: error: class, interface, or enum expected
}
^
Main.java:55: error: class, interface, or enum expected
addEdges($firstJump, $firstJump, $maxIsland, $dag);
^
Main.java:56: error: class, interface, or enum expected
return $dag;
^
Main.java:57: error: class, interface, or enum expected
}
^
Main.java:61: error: class, interface, or enum expected
}
^
Main.java:66: error: class, interface, or enum expected
if (!isset($dag[$vert])) {
^
Main.java:68: error: class, interface, or enum expected
}
^
Main.java:70: error: class, interface, or enum expected
for ($i = $init; $i <= $init + 2; $i++) {
^
Main.java:70: error: class, interface, or enum expected
for ($i = $init; $i <= $init + 2; $i++) {
^
Main.java:70: error: class, interface, or enum expected
for ($i = $init; $i <= $init + 2; $i++) {
^
Main.java:72: error: class, interface, or enum expected
if (($newVert > 0) && ($newVert <= $maxIsland) && ($newVert != $vert) && (!isset($dag[$vert][$newVert]))) {
^
Main.java:75: error: class, interface, or enum expected
addEdges($newVert, $i, $maxIsland, $dag);
^
Main.java:76: error: class, interface, or enum expected
}
^
Main.java:82: error: class, interface, or enum expected
$queue = array();
^
Main.java:83: error: class, interface, or enum expected
foreach ($dag as $vert => $data) {
^
Main.java:86: error: class, interface, or enum expected
}
^
Main.java:89: error: class, interface, or enum expected
return $stack;
^
Main.java:90: error: class, interface, or enum expected
}
^
Main.java:94: error: class, interface, or enum expected
$adj_list = array_keys($dag[$vert]);
^
Main.java:95: error: class, interface, or enum expected
foreach ($adj_list as $adj) {
^
Main.java:98: error: class, interface, or enum expected
}
^
Main.java:101: error: class, interface, or enum expected
}
^
50 errors