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

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       16 396×

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.

Reklama
Reklama

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    

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ý