Google Code Jam 2008 – kvalifikace

Školení, která pořádám

Článek vyšel na serveru Programujte.com.

Google Code Jam po cvičení pokračuje kvalifikací.

Přepínání vyhledávačů

Dotazy
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
Vyhledávače
Yeehaw
NSM
Dont Ask
B9
Googol

Zadání: Věděli jste, že když do vyhledávače Google zadáte „Google“, tak se zhroutí vesmír? Tedy ne v naší realitě, ale v nějaké alternativní. Proto byl navržen centrální systém, který zpracovává všechny dotazy a rozděluje je mezi jednotlivé vyhledávače tak, aby ke zhroucení vesmíru nedošlo. Změna vyhledávače je náročná, proto je naším cílem počet těchto přepnutí minimalizovat. Úkolem úlohy je ze zadaného seznamu vyhledávačů a dotazů zjistit minimální možný počet přepnutí (neboli zjistit, jakých vyhledávačů a v jakém pořadí se máme dotázat). Řešení

Jízdní řád

Zastávka B
12:0215:05
09:0010:35
Zastávka A
09:0012:05
10:0013:05
11:0012:35

Zadání: Vlaková trať má dvě zastávky A a B. Vlaky po trati jezdí podle jízdního řádu. Vlaky jezdí různou rychlostí a na trati se mohou předjíždět. Vlaky nezajíždí do jiných zastávek a nemohou jezdit mimo jízdní řád. Naším úkolem je zjistit, kolik vlaků musí dopravce ráno připravit do obou zastávek, aby mohly jezdit podle jízdního řádu. Řešení

Plácačka na mouchy

ukázka rakety Zadání: Mějme kruhovou tenisovou raketu bez rukojeti s rámem a výpletem začínajícím ve středu rakety. Touto raketou se snažíme trefit mouchu. Zadaný je poloměr mouchy, poloměr rakety, šířka rámu, poloměr výpletových vláken a jejich rozestup. Naším úkolem je zjistit, jaká je pravděpodobnost trefení mouchy, pokud moucha letí na náhodném místě a svým středem vždy letí uvnitř vnějšího okraje rakety. Řešení

Jakub Vrána, Výuka, 15.8.2008, diskuse: 4 (nové: 0)

Diskuse

Gimli2:

Nastin analytickeho reseni placacky na mouchy. Predstava vychazi z nacrtku: http://img518.imageshack.us/img518/9184/placackanamouchufj5.jpg (cely pripad budeme reset jen na 1/4 kruhu, protoze pomer ploch a tedy i sance zasazeni mochy bude stejna)

Sance, ze moucha proleti je pomer zlute ku zelene plose (napr. X) na stretim obrazku. Trefeni je tedy pravdepodobne s P = 1-X.
Aby moucha zasazena nebyla, musi mit svuj stred dostatecne daleko od hran vypletu a samotne rakety. Na prvnim z obrazku jsou to ta bila mista.

Vyuzijeme logicke operace rozdil nad plosnymi objekty. Od zlute kruznice (s polomerem R-t-f) postupne odecteme svisle a lezate obdelniky o rozmeru 2(r+f)×(R-t-f). Vzdalenost mezi jejich stredy je g+2r. A cele jsou posunuty o r+f doleva. Z prvniho zleva a zespodu je tak vlastne jen pulka.

Plosny objekt muze byt reprezentovan mnozinou bodu a mnozinou jejich spojnic. Kazda spojnice muze byt bud usecka, nebo oblouk z kruznice s polomerem R-t-f a stredem v pocatku souradnic. Objekt nemusi byt souvisly. Pak jeho casti nazyvejme treba subobjekty.
Kazdy subobjekt (ctverecek ve vypletu, pripadne serizly kruznici) bude mit 3 nebo 4 vrcholy a 4 nebo 3 usecky a 0 nebo 1 oblouk.

Pro samotny vypocet rozdilu spocitame prusecik dane kruznice s obdelnikem (pro svisle budou pruseciky jen na svislych stranach, nebo ve vrcholech; pro lezate to bude analogicky). Tim se nam definuji 4(3) body/vrcholy vznikleho subobjektu a vime, ze spojnice tech 2 pruseciku bude obloukem, ostatni spojnice useckou. Ale logicky rozdil vektorovych objektu uz urcite budou hotove a rychle algoritmy. ;-)

Na zaver bude jen potreba spocitat plochy. Zelena ctvrtkruznice ma plochu 1/4×Pi×(R+f)^2. U zluteho objektu je potreba spocita sumu ploch jednotlivych subobjektu. Ctverecky jsou jasne (pozname je ze nemaji ani jednu spojnici typu oblouk). A serizle ctverecky vypocitame s pomoci integralu jako plochu pod grafem rezajici kruzice zmensenou o obdelnik o sirce nejsirsiho mista subobjektu a vysce od osy x po spodni usecku subobjektu.

Prgat se mi to nechce ;-), ale pokud by clovek nasel hotove reseni rozdilu plosnych objektu, byla by to prace na okamzik...

ikona Jakub Vrána OpenID:

Myšlenkový pochod je správný, prošel jsem ho stejně. Bavit mě tohle řešení přestalo v momentě, kdy bylo potřeba u každého čtverce vypočítat 4 průsečíky s kružnicí (to by ještě šlo) a potom spočítat plochu těch zaoblených trojúhelníků (jeho obsah je součet obsahu trojúhelníku a kruhové úseče).

Taky se mi to nechtělo programovat :-).

ikona Jakub Vrána OpenID:

Tady je kód:

<?php
function swatter_compute($f, $R, $t, $r, $g) {
    $blank = 0;
    $R2 = ($R-$t-$f) * ($R-$t-$f);
    for ($x1 = $r+$f; $x1 < $R-$t-$f; $x1 += $g+2*$r) {
        // 1 left, 2 right, 3 top, 4 bottom
        $x2 = $x1 + $g - 2*$f;
        $y1 = sqrt($R2 - $x1*$x1);
        $y2 = ($x2 < $R-$t-$f ? sqrt($R2 - $x2*$x2) : -$r-$f);
        $squares1 = floor(($y1-$r-$f) / ($g+2*$r));
        $squares2 = floor(($y2+$r+$f) / ($g+2*$r));
        $blank += $squares2 * ($g-2*$f) * ($g-2*$f);
        for ($squares=$squares1; $squares >= $squares2; $squares--) {
            $x3 = $x1;
            $y3 = $y1;
            if ($y1 > $squares * ($g+2*$r) + $r+$g-$f) {
                $y3 = $squares * ($g+2*$r) + $r+$g-$f;
                $x3 = sqrt($R2 - $y3*$y3);
                $blank += ($g - 2*$f) * ($x3 - $x1);
            }
            $x4 = $x2;
            $y4 = $y2;
            if ($y2 < $squares * ($g+2*$r) + $r+$f) {
                $y4 = $squares * ($g+2*$r) + $r+$f;
                $x4 = sqrt($R2 - $y4*$y4);
            } else {
                $blank += ($x2 - $x3) * ($y2 - $squares * ($g+2*$r) - $r-$f);
            }
            $blank += ($x4-$x3) * ($y3-$y4) / 2;
            $distance = sqrt(($x4-$x3) * ($x4-$x3) + ($y3-$y4) * ($y3-$y4));
            $alpha = asin($distance/2 / ($R-$t-$f));
            $blank += $R2 * ($alpha - cos($alpha) * sin($alpha));
        }
    }
    return 1 - 4 * $blank / (M_PI*$R*$R);
}
?>

Na malý vstup mi funguje, na velký bohužel ne. Nevím, jestli to je jen nedostatečnou přesností nebo nějakou chybou.

ikona Jakub Vrána OpenID:

Jediná komplikace byla v neošetření okrajové podmínky. Takže stačí na začátek funkce přidat <?php if ($g < 2*$f) return 1; ?> a už to správně funguje i pro velký vstup – sláva!

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.