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       10 920×

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 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ý