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

Google Code Jam 2008 - fináleGoogle Code Jam 2008 - finále

 

Google Code Jam 2008 - finále

Google       Google       30. 12. 2008       11 779×

Poslední sada úloh letošního Google Code Jam byla zadaná ve finále. Některé úlohy jsou již obtížnější, ale jiné se stále soustředí spíše na rychlé vymyšlení jednoduchého algoritmu. Na stránkách soutěže se také objevil oficiální klíč k řešení všech dosud zveřejněných soutěžních úloh, kde lze najít podrobnější vysvětlení řešení problémů.

Reklama
Reklama

Džus

Zadání: Na párty jsme pozvali daný počet lidí. Každý z těchto lidí má rád džus namíchaný z přísad A, B a C. Problém je, že každému vyhovuje jiné množství těchto přísad. Naším úkolem je stanovit takové množství přísad, abychom uspokojili co nejvíc lidí. U každého člověka máme zadáno, kolik které přísady minimálně chce, aby mu džus chutnal (maximální součet přísad je stanoven jako číslo 10 000). Řešení

Řešení: U dvou přísad by se dalo postupovat tak, že bychom si do pole $plusminus u každého člověka poznamenali, od jakého do jakého množství jedné přísady mu džus bude chutnat. V tomto poli bychom pak hledali maximální hodnotu. Pro tři přísady stačí vyzkoušet sestavit toto pole pro všechny možné hodnoty třetí přísady.

function juices($people) {
	$return = 0;
	sort($people);
	foreach (array_reverse($people, true) as $key => $val) {
		list($a, $b, $c) = $val;
		$plusminus = array();
		foreach ($people as $val2) {
			list($a2, $b2, $c2) = $val2;
			if ($a + $b2 + $c2 <= 10000) {
				$plusminus[$b2]++;
				$plusminus[10001 - $a - $c2] -= 1;
			}
		}
		ksort($plusminus);
		$value = 0;
		foreach ($plusminus as $val) {
			$value += $val;
			$return = max($return, $value);
		}
		unset($people[$key]);
	}
	return $return;
}

Pro dekrementaci pole $plusminus se nepoužívá operátor --, ale konstrukce -= 1. Důvodem je, že hodnotu null operátor -- nesníží.

Pingpongové balónky

schéma Zadání: Ve veliké místnosti zadaných rozměrů jsou na všech políčcích totožné pasti na myši. Každá past je nabita dvěma balónky, které se při aktivaci vystřelí na relativně zadané políčko a aktivují past, která na cílovém políčku leží. Naším úkolem je zjistit, kolik pastí se celkem aktivuje, pokud jako první aktivujeme past na určeném políčku. Řešení

Řešení: Funkce začne na startovním políčku a ověří, jestli balónek ještě nevypadl z místnosti a jestli jsme dané políčko už nenavštívili. Pokud ne, tak nejprve aktivuje jeden balónek a potom druhý.

function pingpong($size, $ball1, $ball2, $x, $y, &$hits = array()) {
	if ($x >= 0 && $x < $size[0] && $y >= 0 && $y < $size[1] && !isset($hits["$x:$y"])) {
		$hits["$x:$y"] = true;
		pingpong($size, $ball1, $ball2, $x + $ball1[0], $y + $ball1[1], $hits);
		pingpong($size, $ball1, $ball2, $x + $ball2[0], $y + $ball2[1], $hits);
	}
	return count($hits);
}

Pro vyřešení velkého vstupu by bylo potřeba zjistit, do jakých rohů se míčky vůbec nedostanou, a ve zbytku určit podíl aktivovaných pastí.

Minové pole

schéma Zadání: Na minovém poli jsou rozmístěny miny. Nevíme přesně, kde miny jsou, ale u každého políčka víme, kolik je na něm a v jeho okolí min (celkem na devíti políčcích). Naším úkolem je zjistit, kolik min může být maximálně v prostřední řadě políček (počet řad je vždy lichý). Řešení

Řešení: Osobně bych vyzkoušel všechny možnosti a postupem od větví, které se můžou nejméně rozvětvit, bych se pokusil minimalizovat čas testování. Existuje ale i elegantnější řešení – počet min v prostřední řadě totiž přímo plyne z mapy čísel. Stačí si uvědomit, že počet min v každé devítici políček je určen číslem uprostřed tohoto čtverce (pro krajní šestice to určuje prostřední políčko u okraje). Takto můžeme zjistit počet min v každé trojici řad a tím pádem i v horních a dolních (N + 1) / 2 řadách. A když od součtu těchto řad (kde je prostřední řada dvakrát) odečteme celkový počet min získaný stejným způsobem, máme přesně počet min v prostřední řadě.

function mines($number) {
	$cols = count($number);
	$return = 0;
	for ($i = ($cols % 3 ? 0 : 1); $i < $cols; $i += 3) {
		$return += $number[$i];
	}
	return $return;
}

function minelayer($numbers) {
	$rows = count($numbers);
	$return = 0;
	for ($j = ($rows + (($rows - 1) % 6 ? 1 : 3)) / 2; $j < $rows; $j += 3) {
		$return += mines($numbers[$j]);
		$return += mines($numbers[$rows - $j - 1]);
	}
	for ($j = ($rows % 3 ? 0 : 1); $j < $rows; $j += 3) {
		$return -= mines($numbers[$j]);
	}
	return abs($return);
}

Pokud je polovina počtu řádek dělitelná třemi, tak prostřední řádku nelze lehce započítat dvakrát, dá se ale naopak velmi snadno vynechat. Z tohoto důvodu se na konci funkce vrací absolutní hodnota rozdílu.

Stavitelé mostů

schéma Zadání: Máme zadanou mapu, kde je na každém čtverečku les, voda nebo pole. Mezi čtverečky je voda. Naším cílem je propojit tyto ostrovy pomocí mostů, které z daného políčka můžou vést vždy jen na horní, dolní, levý nebo pravý ostrov. Mosty se staví ze dřeva nalezeného v lese a postavit most trvá člověku tolik hodin, jaká je vzdálenost od nejbližšího lesa k propojovanému ostrovu. Na mapě na začátku nejsou žádné mosty a začínáme v levém horním rohu, kde je vždy les. Naším úkolem je propojit všechny ostrovy za minimální počet člověko-hodin a vrátit tento počet. Řešení

Řešení: Mapu budeme procházet do šířky a u každého políčka si poznamenáme, jak je daleko od nejbližšího lesa. Jakmile dorazíme do nějakého lesa, zapíšeme do něj nulu, ale nesmíme zapomenout připočítat cestu, kterou jsme museli urazit z předchozího lesa. Výsledkem je potom součet vzdáleností všech políček od nejbližšího lesa a napočítaných cest mezi lesy.

function bridges($map) {
	$queue = array(array(0, 0, 0));
	$return = 0;
	$distances = array();
	while ($queue) {
		$val = min($queue);
		unset($queue[array_search($val, $queue)]);
		list($distance, $y, $x) = $val;
		if (isset($map[$y]{$x}) && $map[$y]{$x} != '.' && (!isset($distances["$y:$x"]) || $distance < $distances["$y:$x"])) {
			if ($map[$y]{$x} == 'T') {
				$return += floor(($distance + 2) / 2) * ceil($distance / 2);
				$distance = 0;
			}
			$distances["$y:$x"] = $distance;
			$queue[] = array($distance+1, $y-1, $x);
			$queue[] = array($distance+1, $y+1, $x);
			$queue[] = array($distance+1, $y, $x-1);
			$queue[] = array($distance+1, $y, $x+1);
		}
	}
	return $return + array_sum($distances);
}

V každém průchodu cyklem se hledá nejmenší prvek pomocí funkcí min a array_search, využívají se přitom pravidla pro porovnávání polí. Nové ostrovy ke zkontrolování by se do pole $queue mohly zatřiďovat, což by trvalo jen O(log n) místo O(n). Algoritmus je ale dost rychlý i bez toho.

Pro započtení vzdálenosti mezi lesy se používá součet posloupnosti každého druhého čísla. Protože pokud to do lesa bylo např. 5 hodin, tak 5 přepíšeme na 0 (rozdíl 5), 4 na 1 (rozdíl 3) a 3 na 2 (rozdíl 1).

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

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

Reklama
Reklama
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.

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ý