× Aktuálně z oboru

Vychází Game Ready ovladače pro Far Cry 5 [ clanek/2018040603-vychazi-game-ready-ovladace-pro-far-cry-5/ ]
Celá zprávička [ clanek/2018040603-vychazi-game-ready-ovladace-pro-far-cry-5/ ]

Google Code Jam 2008 - kvalifikace

[ http://programujte.com/profil/13839-jakub-vrana/ ]Google [ ?rel=author ]       [ http://programujte.com/profil/118-zdenek-lehocky/ ]Google [ ?rel=author ]       15. 8. 2008       18 153×

Google Code Jam [ http://code.google.com/codejam/ ] po cvičení [ ?akce=clanek&cl=2008080700-google-code-jam-2008-cviceni ] pokračuje kvalifikací [ http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw ].

Přepínání vyhledávačů

VyhledávačeDotazy
Yeehaw
NSM
Dont Ask
B9
Googol
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol

Zadání: Věděli jste, že když do vyhledávače Google zadáte „Google“, tak se zhroutí vesmír? Tedy ne v naší realitě, ale v nějaké alternativní. Proto byl navržen centrální systém, který zpracovává všechny dotazy a rozděluje je mezi jednotlivé vyhledávače tak, aby ke zhroucení vesmíru nedošlo. Změna vyhledávače je náročná, proto je naším cílem počet těchto přepnutí minimalizovat. Úkolem úlohy je ze zadaného seznamu vyhledávačů a dotazů zjistit minimální možný počet přepnutí (neboli zjistit, jakých vyhledávačů a v jakém pořadí se máme dotázat). Řešení [ #kvalifikace-a ]

Řešení: Bohužel nejde použít hladový algoritmus, protože dlouhá posloupnost ukrojená na začátku by nám mohla zkomplikovat situaci v budoucnu. Proto raději vyzkoušíme všechny možnosti:

function switches($engines, $queries, &$switches_queries) {
	$min_switches = null;
	foreach ($engines as $engine) {
		$pos = array_search($engine, $queries);
		if ($pos === false) {
			return 0;
		} elseif ($pos) {
			$switches = &$switches_queries[count($queries) - $pos][$engine];
			if (!isset($switches)) {
				$switches = switches($engines, array_slice($queries, $pos), $switches_queries);
			}
			if (!isset($min_switches) || $min_switches > $switches) {
				$min_switches = $switches + 1;
			}
		}
	}
	return $min_switches;
}

V  kódu je použitá funkce array_search, která mezi dotazy hledá název aktuálního vyhledávače. Pokud ho nenajde, tak jsme hotovi, protože pro zbylé dotazy už vyhledávač nemusíme měnit. Pokud ho naopak najdeme hned na začátku, tak už nic nezkoušíme, protože bychom se dostali do nekonečné smyčky. V jiných případech vyzkoušíme pro zbylé dotazy všechny vyhledávače.

Stejně jako u pouštění vajíček [ ?akce=clanek&cl=2008080700-google-code-jam-2008-cviceni#c ] se používá dynamické programování, abychom nemuseli kratší posloupnosti počítat pořád dokola. Keš ale nedržíme ve statické proměnné, protože po sobě následující úlohy mohou používat různé vyhledávače, pro které se počet změn samozřejmě může lišit. Místo toho se používá parametr předávaný referencí, kterému bohužel v PHP nejde určit výchozí hodnota, takže je před zavoláním funkce potřeba tuto proměnnou nainicializovat na prázdné pole (mohla by to dělat obálková funkce).

Jízdní řád

Zastávka AZastávka B
09:00 – 12:0512:02 – 15:05
10:00 – 13:0509:00 – 10:35
11:00 – 12:35

Zadání: Vlaková trať má dvě zastávky, A a B. Vlaky po trati jezdí podle jízdního řádu. Vlaky jezdí různou rychlostí a na trati se mohou předjíždět. Vlaky nezajíždí do jiných zastávek a nemohou jezdit mimo jízdní řád. Naším úkolem je zjistit, kolik vlaků musí dopravce ráno připravit do obou zastávek, aby mohly jezdit podle jízdního řádu. Řešení [ #kvalifikace-b ]

Řešení je přímočaré:

/** Výpočet počtu vlaků potřebných v jednotlivých stanicích
* @param array $departures pole s prvky $departure_time => array(array("from" => $station, "arrival" => $arrival_time), ...), časy zadané v minutách
* @return array dvouprvkové pole s potřebnými počty vlaků v jednotlivých stanicích
*/
function timetable($departures) {
	$needed = array(0, 0);
	$going = array();
	$available = array(0, 0);
	ksort($departures);
	foreach ($departures as $departure => $trains) {
		foreach ($going as $key => $train) {
			if ($train["arrival"] <= $departure) {
				$available[1 - $train["from"]]++;
				unset($going[$key]);
			}
		}
		foreach ($trains as $train) {
			if (!$available[$train["from"]]) {
				$needed[$train["from"]]++;
			} else {
				$available[$train["from"]]--;
			}
			$going[] = $train;
		}
	}
	return $needed;
}

Projdeme seznam všech odjezdů a pro každý nejprve zjistíme, jestli už se nevrátil nějaký vlak. Potom pro všechny vlaky odjíždějící v daný čas zjistíme, jestli v zastávce máme k dispozici nějakou soupravu ($available) a pokud ne, tak si poznamenáme, že budeme potřebovat o jednu navíc ($needed). Aktuální vlak si přidáme do jedoucích vlaků ($going).

Plácačka na mouchy

Zadání: Mějme kruhovou tenisovou raketu bez rukojeti s rámem a výpletem začínajícím ve středu rakety. Touto raketou se snažíme trefit mouchu. Zadaný je poloměr mouchy, poloměr rakety, šířka rámu, poloměr výpletových vláken a jejich rozestup. Naším úkolem je zjistit, jaká je pravděpodobnost trefení mouchy, pokud moucha letí na náhodném místě a svým středem vždy letí uvnitř vnějšího okraje rakety. Řešení [ #kvalifikace-c ]

K řešení úlohy lze přistoupit několika způsoby. Jednak můžeme pravděpodobnost přesně vypočítat jako poměr obsahu volné plochy a plochy celé rakety (se zohledněním mouchy), to je ale poměrně pracné. Druhou možností je raketu bombardovat náhodnými mouchami a vždycky jen zjistit, jestli raketu trefila:

define("TRIES", 1e6);
define("MT_RAND_MAX", mt_getrandmax());

function swatter_string($x, $f, $r, $g) {
	$center = round($x / ($g+2*$r)) * ($g+2*$r);
	return ($x > $center - $r - $f && $x < $center + $r + $f);
}

function swatter_rand($f, $R, $t, $r, $g) {
	$hits = 0;
	$tries = 0;
	for ($i=0; $i < TRIES; $i++) {
		$x = $R * mt_rand() / MT_RAND_MAX;
		$y = $R * mt_rand() / MT_RAND_MAX;
		$distance = $x*$x + $y*$y;
		if ($distance < $R*$R) {
			$tries++;
			if ($distance > ($R-$t-$f) * ($R-$t-$f) || swatter_string($x, $f, $r, $g) || swatter_string($y, $f, $r, $g)) {
				$hits++;
			}
		}
	}
	return $hits / $tries;
}

Postupně generujeme dvojice náhodných čísel pro souřadnice X a Y. Pokud splňují podmínku, že jsou uvnitř rakety, tak zjistíme, jestli strefí rám rakety nebo svislá či vodorovná lanka výpletu. Nakonec jen vrátíme poměr tref a počtu úspěšných pokusů. Problém tohoto přístupu spočívá v tom, že úplné zadání toleruje absolutní nebo relativní chybu jen 10-6, pro jejíž dosažení bychom museli provést tolik pokusů, že by skript běžel neúměrně dlouho.

Proto vyzkoušíme ještě jedno řešení, nazveme ho numerické. Budeme postupovat po ose Y a v každém bodě zjistíme šířku rakety a šířku překážek na raketě v daném bodě.

function swatter_numeric($f, $R, $t, $r, $g) {
	if ($g <= 2*$f) {
		return 1;
	}
	$hits = 0;
	$tries = 0;
	$R_in = $R-$t-$f;
	$y_center = 0;
	for ($y=$R/TRIES; $y < $R; $y += $R/TRIES) {
		if ($y - $y_center >= $g/2+$r) {
			$y_center += $g+2*$r;
		}
		$tries += sqrt($R*$R - $y*$y);
		if ($y < $R_in && ($y < $y_center - $r - $f || $y > $y_center + $r + $f)) {
			$x = sqrt($R_in*$R_in - $y*$y);
			$squares = (int) (($x+$f+$r) / ($g+2*$r));
			$hits += $squares * ($g-2*$f);
			$hits += max(0, $x - $squares * ($g+2*$r) - $r - $f);
		}
	}
	return 1 - $hits / $tries;
}

Článek stažen z webu Programujte.com [ http://programujte.com/clanek/2008080800-google-code-jam-2008-kvalifikace/ ].