Google Code Jam 2008 - cvičení semifinále
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
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 486×

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

Reklama
Reklama
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.

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.

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ý