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.