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

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

 

Google Code Jam 2008 - semifinále

Google       Google       28. 12. 2008       11 154×

Google Code Jam se blíží do finále, kterému předcházelo asijské, americké a evropské semifinále. Přiznám se, že některé úlohy už byly nad mé síly, v tomto článku proto uvádím pouze výběr úloh z Asie a Evropy.

Reklama
Reklama

Co jsou ptáci?

VýškaHmotnostZvíře
10001000pták
20001000pták
10002000pták
15002010nepták

Zadání: Snažíme se přijít na to, která zvířata v lese jsou ptáci a která ne. Víme, že pokud má zvíře výšku a hmotnost v určitém intervalu, tak je to určitě pták. Tyto dva intervaly nicméně neznáme. Vědci nám dali alespoň seznam zvířat s danou výškou a hmotností a u každého uvedli, zda je to pták, nebo ne. Na základě tohoto seznamu můžeme následně u ostatních zvířat zjistit, zda jde s jistotou o ptáka, nebo to určitě pták není, nebo zda to na základě zadaných dat nelze určit. Řešení

Řešení: Nejprve vyřešíme dva okrajové případy:

  1. Pokud má objekt stejnou výšku a hmotnost jako nějaký nepták, tak je to určitě taky nepták.
  2. Pokud jsme nedostali žádný exemplář ptáka, tak u ostatních zvířat druh určitě nedokážeme určit.

Pokud má zvíře výšku i hmotnost v rozsahu minima a maxima těchto hodnot u předaných ptáků, tak to určitě také bude pták. Nejsložitější je vymyslet podmínku, která rozliší, zda se jedná o neptáka, nebo zda to nedokážeme určit:

  • Pokud má zvíře správnou hmotnost, ale výšku má nižší než nějaký menší nepták nebo naopak vyšší než větší nepták, tak jde určitě také o neptáka.
  • Totéž platí s prohozenou výškou a hmotností.
  • Pokud má navíc zvíře výšku nižší než menší nepták (nebo vyšší než větší nepták) a zároveň hmotnost nižší než lehčí nepták (nebo vyšší než těžší nepták), tak jde určitě také o neptáka.

V jiném případě výsledek nedokážeme určit.

function birds($birds, $not_birds, $test) {
	$weights = array();
	$heights = array();
	foreach ($birds as $bird) {
		list($heights[], $weights[]) = $bird;
	}
	$return = "";
	foreach ($test as $bird) {
		if (in_array($bird, $not_birds)) {
			$return .= "NOT BIRD\n";
		} elseif (!$birds) {
			$return .= "UNKNOWN\n";
		} elseif ($bird[0] >= min($heights) && $bird[0] <= max($heights) && $bird[1] >= min($weights) && $bird[1] <= max($weights)) {
			$return .= "BIRD\n";
		} else {
			foreach ($not_birds as $val) {
				list($height, $weight) = $val;
				if (($weight >= min($weights) && $weight <= max($weights) && ($height < min($heights) ? $bird[0] <= $height : $bird[0] >= $height))
				|| ($height >= min($heights) && $height <= max($heights) && ($weight < min($weights) ? $bird[1] <= $weight : $bird[1] >= $weight))
				|| ((($bird[0] <= $height && $height < min($heights)) || ($bird[0] >= $height && $height > max($heights)))
					&& (($bird[1] <= $weight && $weight < min($weights)) || ($bird[1] >= $weight && $weight > min($weights)))
				)) {
					$return .= "NOT BIRD\n";
					continue 2;
				}
			}
			$return .= "UNKNOWN\n";
		}
	}
	return $return;
}

Algoritmus by se dal ještě optimalizovat (minimálně vypočtením minima a maxima před cyklem), ale není to potřeba.

Barvení plotu

BarvaZačátekKonec
modrá16000
červená400010000
oranžová30008000

Zadání: Máme plot s 10 000 laťkami a chceme ho nabarvit. K dispozici máme několik nabídek na obarvení jednotlivých částí plotu různými barvami. Naším úkolem je zjistit, jestli lze celý plot nabarvit nejvíce 3 barvami a pokud ano, tak vrátit minimální počet nabídek, které za tím účelem musíme přijmout. Řešení

Řešení: Při barvení plotu budeme postupovat zleva doprava. Nabídky si setřídíme podle začátku barvení a prohledáme jenom ty, které začínají před první nenabarvenou laťkou. Podobně si nevšímáme nabídek, které nás v barvení neposunou dál a jen přebarví již nabarvený úsek. Tím významně snížíme počet prohledávaných kombinací, takže úlohu vyřešíme i pro velký vstup.

/** Nabarvení plotu s 10 000 laťkami maximálně třemi barvami
* @param array $offers pole ve tvaru array($zacatek => array($konec => $barva)) seřazené podle $zacatek a potom podle $konec sestupně
* @return int minimální počet nabídek nutných pro nabarvení plotu nebo 10 001, pokud plot nabarvit nelze
*/
function fence($offers, $start = 1, $colors = array(), $count = 0) {
	if ($start > 10000) {
		return $count;
	}
	$return = 10001;
	foreach ($offers as $a => $offer) {
		if ($a > $start) {
			break;
		}
		foreach ($offer as $b => $color) {
			if ($b < $start) {
				break;
			}
			$offers[$a] = array_slice($offers[$a], 1, null, true);
			if (isset($colors[$color]) || count($colors) < 3) {
				$return = min($return, fence($offers, $b + 1, $colors + array($color => true), $count + 1));
			}
		}
		$offers = array_slice($offers, 1, null, true);
	}
	return $return;
}

Funkce array_slice($offers, 1, null, true) se používá místo array_shift proto, že zachová přiřazení klíčů.

Milionář

Zadání: Byli jsme pozváni do soutěže s daným počtem kol, kde v každém kole můžeme vsadit libovolný obnos, který máme k dispozici. S předem známou pravděpodobností tento obnos buď zdvojnásobíme, nebo o něj přijdeme. Naším cílem je vsázet tak, abychom s co největší pravděpodobností vyhráli jeden milion. Hru začínáme s určitým obnosem a naším úkolem je určit pravděpodobnost, že vyhrajeme kýžený milion, pokud budeme sázet optimálně. Řešení

Řešení: Pro začátek je dobré si uvědomit, že pokud už do konce zbývá jen jedno kolo, musíme mít alespoň 500 tisíc. Naopak libovolná vyšší částka, menší než milion, nám nijak nepomůže. Stejně tak dvě kola před koncem musíme vsadit 250 tisíc, takže dává smysl mít částky 250, 500 nebo 750 tisíc. V jednotlivých kolech se tedy stačí držet těchto hranic.

Potom už stačí jen vyzkoušet všechny možnosti vsázení po těchto hranicích.

function millionaire($rounds, $probability, $money, &$cache = array()) {
	if ($money >= 1e6) {
		return 1;
	} elseif (!$rounds || !$probability) {
		return 0;
	}
	$return = &$cache[$rounds][$money];
	if (!isset($return)) {
		$return = 0;
		$margin = 1e6 / (1 << ($rounds – 1));
		for ($loose = $margin * floor($money / $margin); $loose >= 0; $loose -= $margin) {
			$win = $margin * floor((2*$money – $loose) / $margin);
			$p = $probability * millionaire($rounds – 1, $probability, $win, $cache) + (1 – $probability) * millionaire($rounds – 1, $probability, $loose, $cache);
			if ($p >= $return) {
				$return = $p;
			} else {
				break;
			}
		}
	}
	return $return;
}

Pro vyřešení velkého vstupu bylo potřeba využít cache a kromě toho si uvědomit, že pokud při zvýšení sázky klesne pravděpodobnost celkové výhry, tak už není částku nutné dále zvyšovat. Tím pádem lze začít u nejnižších sázek a není potřeba prozkoumat všechny možnosti.

Autobusové zastávky

Zadání: Na Marsu je N autobusových zastávek v řadě za sebou, vzájemně od sebe vzdálených 1 km. K dispozici máme K autobusů a naším úkolem je zjistit počet možných jízdních řádů, pokud jsou zadané následující podmínky:

  • Ráno jsou autobusy na prvních K zastávkách.
  • Autobusy jezdí pouze zleva doprava.
  • Večer musí být autobusy na posledních K zastávkách.
  • V každé zastávce musí během dne zastavit právě jeden autobus.
  • Jeden autobus může na jednu jízdu dojet jen do P kilometrů vzdálené zastávky.

Takových jízdních řádů samozřejmě může existovat obrovské množství, proto nám stačí vrátit jen zbytek po dělení číslem 30031. Řešení

Řešení: Při řešení budeme postupovat zleva doprava a budeme se soustředit na to, abychom obsadili první neobsazenou zastávku. To budeme opakovat tak dlouho, dokud nedojedeme na konec trasy.

/** Nalezení počtu jízdních řádů
* @param int $n počet zastávek
* @param array $buses pozice autobusů v zastávkách
* @param array $p maximální vzdálenost, kterou autobus najednou ujede
* @return int počet různých jízdních řádů modulo 30031
*/
function bus_stops($n, $buses, $p, &$cache = array()) {
	$next = max($buses) + 1;
	if ($next > $n) {
		return (reset($buses) > $n – count($buses) ? 1 : 0);
	}
	$return = 0;
	foreach ($buses as $key => $val) {
		$buses2 = $buses;
		array_splice($buses2, $key, 1);
		$buses2[] = $next;
		$x = &$cache[serialize($buses2)];
		if (!isset($x)) {
			$x = bus_stops($n, $buses2, $p, $cache);
		}
		$return += $x;
		if ($val + $p == $next || $next == $n) {
			break;
		}
	}
	return $return % 30031;
}

Prozkoumané možnosti se ukládají do cache, kde se jako klíč používá serializované pole. To není úplně nejšikovnější, protože serializace je poměrně časově náročná, ale pro vyřešení malého vstupu to stačí. Pro velký vstup bychom museli zvolit chytřejší přístup – napadá mě, že vzhledem k nízké maximální hodnotě P (10) by se daly prozkoumat všechny P-tice a výsledek odvodit z počtu přechodů mezi nimi.

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

4 názory  —  4 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

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ý