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

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín

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

Google       Google       29. 10. 2008       17 188×

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

Reklama
Reklama
Obrázek ke článku NopCommerce – datová vrstva a přístup k datům – 2. díl

NopCommerce – datová vrstva a přístup k datům – 2. díl

V minulém článku jsme si představili platformu NopCommerce z globálního pohledu. V dnešním díle se již zaměříme na konkrétní část systému, a to datovou vrstvu. Představíme si základní stavební kameny systému v podobě doménových objektů. Ukážeme si, jakým způsobem rozšířit doménové objekty a jakým způsobem přistupuje NopCommerce k nastavení systému a modulů.

Obrázek ke článku Seznamte se s open source platformou NopCommerce – 1. díl

Seznamte se s open source platformou NopCommerce – 1. díl

Hledáte e-commerce řešení, které si dokážete přizpůsobit podle vašich požadavků? Chcete čistý a srozumitelný kód, se kterým bude radost pracovat? Prozkoumejte s námi možnosti open source projektu NopCommerce. Seriál programování pod NopCommerce vám pomůže překonat první kroky nejistoty a úspěšně zvládnout vývoj pod platformou NopCommerce.

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