× Aktuálně z oboru

Programátoři po celém světě dnes slaví Den programátorů [ clanek/2018091300-programatori-po-celem-svete-dnes-slavi-den-programatoru/ ]
Celá zprávička [ clanek/2018091300-programatori-po-celem-svete-dnes-slavi-den-programatoru/ ]

Google Code Jam 2008 - kolo 1A

[ http://programujte.com/profil/13839-jakub-vrana/ ]Google [ ?rel=author ]       [ http://programujte.com/profil/118-zdenek-lehocky/ ]Google [ ?rel=author ]       24. 8. 2008       16 773×

Google Code Jam [ http://code.google.com/codejam/ ] po cvičení [ ?akce=clanek&cl=2008080700-google-code-jam-2008-cviceni ] a kvalifikaci [ ?akce=clanek&cl=2008080800-google-code-jam-2008-kvalifikace ] pokračuje prvním kolem [ http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiE2QUM ].

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í [ #kolo1a-a ]

Ř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 [ http://www.php.net/manual/en/book.bc.php ].

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í [ #kolo1a-b ]

Ř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í [ #kolo1a-c ]

Ř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 [ http://www.php.net/manual/en/book.bc.php ]. 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.


Článek stažen z webu Programujte.com [ http://programujte.com/clanek/2008080801-google-code-jam-2008-kolo-1a/ ].