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 515×

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 NEWTON Media prohledá 200  milionů mediálních zpráv během sekund díky Cisco UCS

NEWTON Media prohledá 200 milionů mediálních zpráv během sekund díky Cisco UCS

Česká společnost NEWTON Media provozuje největší archiv mediálních zpráv ve střední a východní Evropě. Mezi její zákazníky patří například ministerstva, evropské instituce nebo komerční firmy z nejrůznějších oborů. NEWTON Media rozesílá svým zákazníkům každý den monitoring médií podle nastavených klíčových slov a nabízí online službu, kde lze vyhledat mediální výstupy v plném znění od roku 1996.

Reklama
Reklama
Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

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 © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý