Google Code Jam 2008 – kolo 1A

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

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

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

<?php
/** Určení sladových příchutí koktejlů
* @param int počet různých příchutí
* @param array 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.

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

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