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

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

 

Google Code Jam 2008 - semifinále

Google       Google       28. 12. 2008       11 232×

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

Obrázek ke článku Dovozci baterií mění logistiku, letadlo nahrazuje námořní doprava

Dovozci baterií mění logistiku, letadlo nahrazuje námořní doprava

Dovozci baterií do mobilů či notebooků upouštějí od letecké přepravy zboží. V letošním roce plánují dovézt až 80 % produktů lodí. Přitom před 5 lety byla většina baterií do mobilních přístrojů dovezených do České republiky přepravována letadlem. Za proměnou způsobu transportu akumulátorů stojí zpřísnění pravidel pro leteckou přepravu, která přinášejí vyšší náklady i náročnou agendu.

Reklama
Reklama
Obrázek ke článku JIC otevírá největší digitální dílnu pro veřejnost v České republice

JIC otevírá největší digitální dílnu pro veřejnost v České republice

JIC otevírá první nonstop veřejně dostupnou digitální dílnu světového formátu s vybavením za 3 miliony korun. Dílnu může využívat po registraci kdokoliv. V  prostorách vzniknou prototypy produktů místních startupů, projekty kutilů a studentů i umělecká díla. Cílem dílny je zpřístupnit veřejnosti drahé přístroje a přitáhnout více podnikavých lidí k technickým oborům.

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.

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ý