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

Ř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í:

<?php
function magician($white, $black) {
    return ($black % 2 ? "BLACK" : "WHITE");
}
?>

Ř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ý:

<?php
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í:

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

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

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