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       17 618×

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

Nové články

Reklama
Reklama
Obrázek ke článku Bezrealitky.cz na novém webu rychleji propojí vážné zájemce s majiteli nemovitostí

Bezrealitky.cz na novém webu rychleji propojí vážné zájemce s majiteli nemovitostí

Největší platforma pro přímý prodej a pronájem domů a bytů Bezrealitky.cz představila novou podobu svého portálu. Redesign zásadně zjednodušuje všechny transakce, mění způsob, jakým zájemci o bydlení komunikují s majiteli nemovitostí, přináší nejpřesnější filtrování nabídek na trhu, ale také umožňuje prověřovat důvěryhodnost zájemců. 

Obrázek ke článku Samba.ai: Personalizační nástroje hlásí připravenost na GDPR

Samba.ai: Personalizační nástroje hlásí připravenost na GDPR

Do ostrého nasazení nařízení GDPR, které upravuje nakládání s osobními údaji, zbývá pár dní, a vzbuzuje vrásky u řady provozovatelů služeb, které pracují s profilací návštěvníků na stránkách a personalizací obsahu. Český personalizační nástroj Samba.ai(dříve Yottly) zajišťující personalizaci webu a prediktivní automatizaci email marketingu je však slovy svého CEO Davida Vyskočila na GDPR plně připraveno. 

Obrázek ke článku Jak se liší metody šifrování dat?

Jak se liší metody šifrování dat?

Jaké výhody má celodiskové a souborové šifrování? A co vám přinese šifrování virtuálního disku? Ochranu důležitých dat řeší firmy různě. Mohou využít přístupových práv, zálohování, VPN nebo šifrování. Právě šifrování považují odborníci na kybernetickou bezpečnost za nejspolehlivější řešení.

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