Google Code Jam 2008 - kvalifikace
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Google Code Jam 2008 - kvalifikaceGoogle Code Jam 2008 - kvalifikace

 

Google Code Jam 2008 - kvalifikace

Google       Google       15. 8. 2008       15 715×

Google Code Jam po cvičení pokračuje kvalifikací.

Reklama
Reklama

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í

Ř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 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í

Ř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í

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

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

2 názory  —  2 nové  
Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Jakub VránaAutorův profesní život se točí převážně kolem PHP. Živí se programováním v tomto jazyce, podílí se na oficiální dokumentaci, vyučuje ho na MFF UK a vede odborná školení. Poznámky si zapisuje na weblog PHP triky.
Web    

Nové články

Obrázek ke článku Nový IT hráč na českém trhu

Nový IT hráč na českém trhu

V roce 2015 otevřela v Praze na Pankráci v budově City Tower své kanceláře společnost EPAM Systems (NYSE:EPAM), jejíž centrála se nachází v USA. Společnost byla založená v roce 1993 a od té doby prošla velkým vývojem a stále roste.

Reklama
Reklama
Obrázek ke článku České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace (CRA) pořádají druhý ročník CRA IoT Hackathonů. Zájemci z řad vývojářů a fanoušků moderních technologií mohou změřit své síly a během jediného dne sestrojit co nejzajímavější funkční prototyp zařízení, které bude komunikovat prostřednictvím sítě LoRa. CRA IoT Hackathony se letos uskuteční ve dvou fázích, na jaře a na podzim, v různých městech České republiky. Jarní běh se odstartuje 31. března v Brně a 7. dubna v Praze.

Obrázek ke článku Cloud computing je využíván stále intenzivněji

Cloud computing je využíván stále intenzivněji

Využívání cloud computingu nabývá na intenzitě. Jen v letošním roce vzroste podle analytiků trh se službami veřejného cloudu o 18 %, přičemž o téměř 37 % vzrostou služby typu IaaS. Růst o více než pětinu pak čeká služby poskytování softwaru formou služby, tedy SaaS. Aktuálním trendům v oblasti využívání cloudu se bude věnovat konference Cloud computing v praxi, která se koná 23. března. 2017 v pražském Kongresovém centru Vavruška na Karlově náměstí 5.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý