Google Code Jam 2008 - kolo 1A
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Google Code Jam 2008 - kolo 1AGoogle Code Jam 2008 - kolo 1A

 
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
Laser Game Brno

Google Code Jam 2008 - kolo 1A

Google       Google       24. 8. 2008       16 607×

Google Code Jam po cvičení a kvalifikaci pokračuje prvním kolem.

Reklama
Reklama

Nejmenší skalární součin

Zadání: Máme dva vektory (x1, x2, …, xn) a (y1, y2, …, yn), jejichž skalární součin je definován jako x1y1 + x2y2 + … + xnyn. Naším úkolem je získat minimální možný skalární součin těchto vektorů, pokud si pořadí jejich souřadnic můžeme uspořádat podle libosti. Řešení

Řešení je jednoduché: stačí si souřadnice vektorů uspořádat podle velikosti a pronásobit spolu největší souřadnici prvního vektoru s nejmenší souřadnicí druhého vektoru, potom druhou největší s druhou nejmenší a tak dále.

function scalar_product($vector1, $vector2) {
	sort($vector1);
	rsort($vector2);
	$product = 0;
	foreach ($vector1 as $key => $v1) {
		$product = bcadd($product, bcmul($v1, $vector2[$key]));
	}
	return $product;
}

U velkého vstupu narazíme na jediný problém – u vysokých čísel se ztrácí požadovaná přesnost, proto používáme knihovnu BC Math.

Mléčné koktejly

Zadání: V obchodě připravujeme mléčné koktejly vyrobené z N příchutí. Každý z nich může být buď sladový nebo bezsladový, celkem tedy dokážeme vyrobit 2N koktejlů. Každý z našich zákazníků má oblíbené nějaké koktejly, z nichž maximálně jeden ve sladové variantě. Musíme připravit N dávek koktejlů (pro každou příchuť) tak, aby si každý zákazník vybral alespoň jeden oblíbený koktejl. Naším úkolem je zjistit, jestli můžeme připravit dávky koktejlů tak, abychom zákazníky uspokojili, a pokud ano, tak které příchutě máme připravit v jaké variantě, aby celkový počet sladových dávek byl co nejmenší. Řešení

Řešení: Vzhledem k tomu, že sladovou příchuť může mít každý zákazník rád jenom jednu, tak stačí vyřešit zákazníky, kteří mají rádi právě jednu příchuť. Tu zafixujeme a projdeme ostatní zákazníky – pokud jim volba vyhovuje, tak se o ně už dál nemusíme starat. Pokud jim nevyhovuje, tak pro ně musíme vyzkoušet jejich ostatní možnosti.

/** Určení sladových příchutí koktejlů
* @param int $tastes počet různých příchutí
* @param array $customers pole $num => array(array($taste => $malted, ...), ...)
* @return array označení sladových koktejlů nebo array("IMPOSSIBLE"), pokud nejde zákazníkům vyhovět
*/
function milkshakes($tastes, $customers) {
	$malted = array_fill(1, $tastes, 0);
	while (($picky = array_pop($customers[1]))) {
		$taste = key($picky);
		$malted[$taste] = reset($picky);
		foreach ($customers as $num => $val) {
			foreach ($val as $key => $customer) {
				if (isset($customer[$taste])) {
					if ($customer[$taste] != $malted[$taste]) {
						if ($num == 1) {
							return array("IMPOSSIBLE");
						}
						unset($customer[$taste]);
						$customers[$num-1][] = $customer;
					}
					unset($customers[$num][$key]);
				}
			}
		}
	}
	return $malted;
}

Zákazníky udržujeme organizované podle počtu příchutí, které mají rádi. Pokud jim vybraná příchuť nevyhovuje, tak je jen přesuneme do vyšší škatulky. Hotovi jsme v momentě, kdy už nemáme vybíravé zákazníky.

N-tá mocnina

Zadání: Naším úkolem je pro zadané n najít poslední tři čísla před desetinnou tečkou v čísle (3 + √5)n. Např. pro n=5 je číslo (3 + √5)5 = 3935.73982…, takže výsledek je 935. Řešení

Řešení: Pro malý vstup stačí číslo jednoduše vypočítat:

function formula_numbers($exp) {
	bcscale(30);
	return bcmod(bcpow(bcadd(3, bcsqrt(5)), $exp), 1000);
}

Kvůli potřebné přesnosti se opět používá knihovna BC Math. Problém je s velkým vstupem, kde n může být až 2 miliardy. Asi by se nějak dala použít funkce bcpowmod, ta ale pracuje jen s celými čísly.

×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 SODAT vidí budoucnost datové bezpečnosti ve strojovém učení

SODAT vidí budoucnost datové bezpečnosti ve strojovém učení

Firmy chrání svá citlivá data často nedostatečně. Podle průzkumu společnosti SODAT se v minulém roce setkalo až 80 % z nich s bezpečnostním incidentem ztráty nebo úniku dat. Jedna z pilotních firem, která testovala novou verzi řešení SODAT Protection & Analytics 2.0pro bezpečností analýzu a monitoring dat díky novince zjistila, kdo z disku smazal důležité výkresy a mohla na incident včas reagovat.

Reklama
Reklama
Obrázek ke článku Kontrolujete pracovní emaily i na dovolené? 7 tipů odborníka, jak nepřijít o data

Kontrolujete pracovní emaily i na dovolené? 7 tipů odborníka, jak nepřijít o data

Letní měsíce jsou pro většinu zaměstnanců spojené s každoroční dovolenou. Z údajů Českého statistického úřadu vyplývá, že v roce 2017 podnikli Češi přes 13 milionů delších cest (tzn. s více než čtyřmi noclehy). Přitom právě na období července, srpna a září připadá více než 7,5 milionů z nich. Nicméně tradiční představu o dovolené jako o čase, kdy má práci na starost někdo jiný, Češi boří. 

Obrázek ke článku 10 SEO mýtů, které už nemusíte v roce 2018 řešit

10 SEO mýtů, které už nemusíte v roce 2018 řešit

„Kolik má být na stránce klíčových slov?“, „Nemáš vyplněný meta tag keywords, to nebude fungovat.“, „Katalogy jsou mrtvý“. Také jste už slyšeli některé z těchto otázek? Pojďme si na ně konečně jednou provždy odpovědět.

Obrázek ke článku Trend Micro pomohlo usvědčit viníky v mezinárodním případu Scan4You

Trend Micro pomohlo usvědčit viníky v mezinárodním případu Scan4You

Společnost Trend Micro Incorporated, globální lídr v oblasti kybernetické bezpečnosti, oznámila podrobnosti o své úzké spolupráci s FBI v případu Scan4You. Trend Micro se podílelo na identifikaci osob, které byly spojeny se službou Scan4You Counter Antivirus, což vedlo k jejich odsouzení.

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