fork download

copy

<?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;
}
 
?>

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

Standard output is empty