# skuska 27.6.2011

<{ForumPost(poster="squo314", timestamp=2011-06-27 13:40:52)}>
zadanie:  
mame krizovatku(=sachovnicu) s autami 8x8. Je zaplnena autami. Na kazdom policku je bud auto, ktore sa pohybuje dolava, alebo auto, ktore hybe hore. Alebe je policko prazdne.  
Na kazdom policku moze byt maximalne jedno auto. Kazdu minutu sa mozu auta pohnut o jedno policko. Ulohou je napisat algorutmus, ktory vypise, ze za kolko minut sa dana krizovatka vyprazdni pri optimalnom pohybe aut.  
(Urcujeme teda, v ktorej minute sa ktore auta maju pohnut a zistujeme pocet minut).  
  
ukazka najlepsieho tahu na krizovatke 3x3.  
Predstavme si pociatocnu poziciu:  
0L0  
0UL  
000  
  
// 0 = prazdne policko, L->left- auto, ktore sa hybe dolava, U->up  
po prvej minute dostaneme:  
LU0  
0L0  
000  
  
teda tato krizovatka sa da vyprazdnit za 3 minuty.  
  
obmedzenie:  
pocet aut <= 20  
pamat 2.8 MB  
-------  
riesenie: moje riesenie sa topferovi na zaciatku nelibilo, lebo mi hadzal rozne kontrapriklady, ale nakoniec som mu ukazal, ze moj algoritmus vsetky tieto kontrapriklady riesi, takze je fakt dobry. Riesenie sa mu teda nakoniec libilo za jedna :)  
  
samotne riesenie:  
cele si to mozem predstavit ako graf, kde vrcholy su dane konfiguracie mapy(rozostavenia aut) a hrany znacia, ze sa z jednej konfiguracie posunutim niektorych aut viem dostat do dalsej konfiguracie.  
Cena hrany bola rovna poctu aut, ktore sa pohli. Ako pozorovanie je zaujimave, ze nech sa hybem v tomto grafe hocijak, pokial sa stale aspon jedno auto pohne, dostanem riesenie.(prazdnu mapu=krizovatku=sachovnicu=konfiguraciu). Ja som postupoval takto: najprv som auta, ktore mozu ist prec z krizovatky, odstranil. Potom som prechadzal celu mapu(z horneho laveho policka ju treba prechadzat dole doprava) a pokial na dane policko moze ist jedno auto, tak ho tam presuniem. Pokial na dane policko mozu ist dve auta(tento stav nazyvam kolizia), tak skusim rekurzivne obe moznosti. Takto vlastne prejdem mapu do hlbky jedna a za najlepsiu konfiguraciu budem povazovat najhodnotnejsiu hranu.  
Tod vse :)  
  
na druhu cast so dostal dokaz zlozitosti porovnavacich triediacich algoritmov, ze su v omega n log n...  
to som nevedel, tak som dostal nahradu vyhodnoceni infixoveho vyrazu...  
  
nakoniec za dva :) Dojmy - bola to pohodova skuska, len trebalo fakt svoj program vediet obhajit :)
<{/ForumPost}>

<{ForumPost(poster="Viki.n", timestamp=2016-05-29 21:25:07)}>
Ahoj, není na tento algoritmus například toto protipříklad?  
P0000  
0U000  
0U000  
Podle mě ti to napřed nechá popojet nahoru obě U auta ikdyž evidentně optimální je pustit v 1. tahu P-auto
<{/ForumPost}>

<{ForumPost(poster="mykem", timestamp=2016-05-30 20:50:02)}>
Ahoj, není, v zadání se píše jen o L-autech a U-autech :)  
  
Ale ani

    00L00
    0U000
    0U000

by protipříkladem nejspíš nebylo, když se v řešení píše, že se při kolizi vyzkouší rekurzivně obě možnosti.
<{/ForumPost}>