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

Google Code Jam 2008 - cvičení semifináleGoogle Code Jam 2008 - cvičení semifinále

 

Google Code Jam 2008 - cvičení semifinále

Google       Google       29. 10. 2008       20 198×

Google Code Jam se přibližuje k semifinále, které probíhá přímo v pobočkách firmy Google. Zatím je možné si ho alespoň vyzkoušet. Úlohy jsou tentokrát velice lehké, což je možná způsobeno tím, že účastníci budou úlohy poprvé řešit v neznámém prostředí a tedy ve větším stresu.

Starý kouzelník

Zadání: Kouzelník dá do klobouku W bílých a B černých koulí a nechá vás vždy vytáhnout dvojici koulí vámi zvolených barev. Pokud vytáhnete koule stejné barvy, vrátíte do klobouku bílou (pokud jste vytáhli dvě černé, dáte do klobouku bílou z rezervní hromady). Pokud vytáhnete dvě různé barvy, vrátíte do klobouku černou. Takto postupujete tak dlouho, až v klobouku zbude jediná koule. Kouzelník samozřejmě nevidí, jaké barvy si v jednotlivých tazích vybíráte. Jeho úkolem je uhodnout, jaká koule v klobouku zbude. Řešení

Řešení: Vypadá to na pěknou rekurentní rovnici, že?

f(W, B):
f(W-1, B-1) -> f(W-1, B)
f(W-2, B) -> f(W-1, B)
f(W, B-2) -> f(W+1, B-2)

Kde se tato rekurence zastaví? Pokud už v klobouku není žádná černá koule, jistě tam nakonec zbude bílá. Pokud je naopak v klobouku jediná černá koule, tak už se jí nezbavíme. No a každý další krok buď počet černých koulí zachová nebo sníží o dva, takže výsledný kód je triviální:

function magician($white, $black) {
	return ($black % 2 ? "BLACK" : "WHITE");
}

Čtvercová pole

Zadání: Máme zadáno N bodů ležících v rovině. Naším úkolem je uzavřít tyto body do K čtverců a vrátit minimální možnou délku hrany těchto čtverců. Strany čtverců musí být vodorovné a svislé, čtverce se mohou libovolně překrývat. Řešení

Řešení: Výsledná délka hrany čtverce bude jistě odpovídat vodorovné nebo svislé vzdálenosti mezi některými dvěma body. Proto si nejprve zjistíme všechny tyto rozestupy a následně metodou půlení intervalů zjistíme, který je ten správný:

function square_fields($k, $points) {
	sort($points);
	$distances = array();
	foreach ($points as $p1) {
		foreach ($points as $p2) {
			$distances[max(abs($p1[0] - $p2[0]), abs($p1[1] - $p2[1]))] = true;
		}
	}
	$distances = array_keys($distances);
	sort($distances);
	$key_min = 1;
	$key_max = count($distances) - 1;
	while ($key_min < $key_max) {
		$key = floor(($key_max + $key_min) / 2);
		if (square_check($k, $distances[$key], $points)) {
			$key_max = $key;
		} else {
			$key_min = $key + 1;
		}
	}
	return $distances[$key_min];
}

Funkce square_check zjistí, jestli lze s danou délkou hrany a daným počtem čtverců pokrýt zadané body. Funkce pracuje rekurzivně – zleva odebírá body a klade je na levou hranu čtverce. Všechny body, které do tohoto čtverce spadnou, se rekurzivnímu volání nepředají:

function square_check($k, $distance, $points) {
	$left = reset($points);
	foreach ($points as $bottom) {
		if ($bottom[0] <= $left[0] + $distance && $bottom[1] <= $left[1] && $bottom[1] >= $left[1] - $distance) {
			$points2 = $points;
			foreach ($points2 as $key => $p) {
				if ($p[0] <= $left[0] + $distance && $p[1] >= $bottom[1] && $p[1] <= $bottom[1] + $distance) {
					unset($points2[$key]);
				}
			}
			if (!$points2 || ($k > 1 && square_check($k - 1, $distance, $points2))) {
				return true;
			}
		}
	}
	return false;
}

Funkce by se dala ještě optimalizovat, ale není to potřeba.

Hamiltonovské kružnice

Hamiltonovský graf Zadání: Máme daný téměř kompletní neorientovaný graf s N vrcholy, ve kterém chybí jen několik hran (které jsou zadané). Naším úkolem je zjistit, kolik je v tomto grafu hamiltonovských kružnic (což je kružnice, která každý vrchol grafu navštíví právě jednou). Řešení

Řešení: Průchod grafem začneme vždy ve vrcholu č. 1. Tento vrchol odebereme a dále budeme postupovat rekurzivně. Po vyčerpání všech vrcholů zjistíme, jestli se lze vrátit zpátky na start a tím cyklus uzavřít.

function cycles($points, $forbidden, $from = 1) {
	unset($points[$from]);
	if (!$points) {
		return (isset($forbidden[$from][1]) ? 0 : 1);
	}
	$return = 0;
	foreach ($points as $to => $val) {
		if (!isset($forbidden[$from][$to])) {
			$return = ($return + cycles($points, $forbidden, $to)) % (2*9901);
		}
	}
	return $return;
}

Výsledek má být vrácen modulo 9901 a kružnice mají být neorientované (algoritmus pracuje orientovaně, proto bude výsledek funkce ještě potřeba vydělit dvěma).

×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     Twitter     Facebook     LinkedIn    

Nové články

Obrázek ke článku Stavebnice umělé inteligence 1

Stavebnice umělé inteligence 1

Článek popisuje první část stavebnice umělé inteligence. Obsahuje lineární a plošnou optimalizaci.  Demo verzi je možné použít pro výuku i zájmovou činnost. Profesionální verze je určena pro vývojáře, kteří chtějí integrovat popsané moduly do svých systémů.

Obrázek ke článku Hybridní inteligentní systémy 2

Hybridní inteligentní systémy 2

V technické praxi využíváme často kombinaci různých disciplín umělé inteligence a klasických výpočtů. Takovým systémům říkáme hybridní systémy. V tomto článku se zmíním o určitém typu hybridního systému, který je užitečný ve velmi složitých výrobních procesech.

Obrázek ke článku Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Vedení týmu v oboru informačních technologií se nijak zvlášť neliší od jiných oborů. Přesto však IT manažeři čelí výzvě v podobě velmi rychlého rozvoje a tím i rostoucími nároky na své lidi. Udržet pozornost, motivaci a efektivitu týmu vyžaduje opravdu pevné manažerské základy a zároveň otevřenost a flexibilitu pro stále nové výzvy.

Obrázek ke článku Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Za poslední rok se podoba práce zaměstnanců změnila k nepoznání. Především plošné zavedení home office, které mělo být zpočátku jen dočasným opatřením, je pro mnohé už více než rok každodenní realitou. Co ale dělat, když se při práci z domova ztrácí motivace, zaměstnanci přestávají komunikovat a dříve fungující tým se rozpadá na skupinu solitérů? Odborníci na personalistiku dali dohromady několik rad, jak udržet tým v chodu, i když pracovní podmínky nejsou ideální.

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý