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

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