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

Google Code Jam 2008 - kvalifikaceGoogle Code Jam 2008 - kvalifikace

 

Google Code Jam 2008 - kvalifikace

Google       Google       15. 8. 2008       15 355×

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 Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

Reklama
Reklama
Obrázek ke článku ICT PRO školení zaměřené nejenom na ICT

ICT PRO školení zaměřené nejenom na ICT

Dovolte, abychom se představili. Jsme zaměstnanci společnosti ICT Pro, profesionálové v oblasti poskytování komplexních ICT služeb. Neboli služeb spojených s informačními a komunikačními technologiemi, které dnes - ve 21. století - tvoří  nedílnou součást běžného provozu všech moderních firem.

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ý