Mili nasi riesitelia,
Dostavaju sa vam do ruk zadania druheho kola. Dufam, ze sa vam budu pacit. Riesenia prikladov nam posielajte najneskor do 11. decembra 2000.
Davno-pradavno, ked este po sirej prerii putovali stada bizonov, zil aj Indian Oten Niw. Tento Indian mal raz blaznivy napad - rozhodol sa zjednotit vsetky indianske kmene. Rozoslal preto k vsetkym kmenom poslov s pozvanim na mierovu poradu. Poslovia sa vsak rychlo vratili. "Pri jednom bizonom stehne s Komancom, Utahom a Kiowom? Ci nevies, ze sme proti nim vykopali bojovu sekeru?? Jedneho by som este zniesol, ale vsetkych tych prasivych psov naraz? Nikdy!!" zvolal nacelnik Siouxov. A tak to bolo so vsetkymi - jednemu sa nepacili ti, druhemu zase ini. Oten sa vsak nevzdal a poslal druhe pozvanie, kde kazdemu slubil, ze viac ako jedneho nepriatela nestretne. A ako to chcel zariadit? Nuz, rozhodol sa, ze zorganizuje viac stretnuti sucasne, jednotlivych nacelnikov rozdeli do skupin a kazdu skupinu pozve na ine miesto. Zorganizovat vsak take stretnutie, to nie je take jednoduche, a preto by skupin malo byt co najmenej.
Teraz sedi nad zoznamom vykopanych bojovych sekier a rozmysla, ako tych tvrdohlavych nacelnikov rozdelit. Sam by na to nestacil, a preto poziadal o pomoc kmenoveho medicinmana. Ten mu odpovedal: (Medzi medicinmanmi je uz tradiciou, ze ich odpovede su sice presne, ale uplne zbytocne) "Vedz, ze i ten najodvaznejsi si netrufne na viac ako troch." Napriek tejto odpovedi Oten neprisiel na nic, a tak sa rozhodol poziadat o pomoc Vas.
Dany je pocet vsetkych kmenov N, pocet znepriatelenych dvojic kmenov M a ich zoznam. Ak je kmen a znepriateleny s kmenom b, znamena to zaroven, ze kmen b je znepriateleny s kmenom a. Kazdy kmen ma, ako uz povedal medicinman, nanajvys troch nepriatelov. Vasou ulohou je najst take rozdelenie kmenov do skupin, aby tych skupin bolo co najmenej a v ramci jednej skupiny mal kazdy kmen nanajvys jedneho nepriatela.
Vstup
N=4, M=4 (1,2), (1,3), (2,3), (2,4)
Vystup
Stacia dve skupiny. V prvej su kmene 1, 3 a v druhej 2, 4.
Raz uradoval v Bratislave na Urade zalezitosti a pokut byrokrat Byrokrat a poslal kazdemu Bratislavcanovi list zhruba tohto obsahu:
"Dostavte sa na Urad zalezitosti a pokut najneskor do 15.9. tohto roku do 14:37 ohladom prejednania zalezitosti c. 578 podla zakona 356/96 z.z. Ak sa nedostavite do uvedeneho datumu, bude vam vyrubena pokuta 823,- Sk." Byrokrat Byrokrat bol dosledny byrokrat. V liste uviedol kazdemu Bratislavcanovi nejaky cas, datum a pokutu. Niektorym ludom mohol uviest rovnaky cas a datum.
Kazde jedno vybavenie na urade trva sice len jednu minutu, ale Bratislavcanov je vela a je preto mozne, ze nie kazdy stihne vybavit svoju ziadost do uvedneho casu a bude platit pokutu. Preto sa pokuste poradit kazdemu Bratislavcanovi, kedy ma prist, aby sucet pokut zaplateny celou Bratislavou bol minimalny.
Je dane N - pocet Bratislavcanov. Dalej je pre kazdeho z nich dane ti (0 <= i <= N) - cas v minutach (merany od teraz), do ktoreho musi clovek stihnut prist na urad. Ak to nestihne, bude platit pokutu pi (0<= i <= N). Vasou ulohu je pre kazdeho Bratislavcana urcit cas v minutach, kedy ma prist na urad tak, aby sucet vsetkych zaplatenych pokut bol najmensi mozny. Navyse, ziadni dvaja Bratislavcania nesmu prist na urad naraz, aby sa nepobili o to, kto prisiel skor.
Vstup
N=5 Terminy: 0 3 2 1 1 Pokuty: 100 10 1 8 9
Vystup
Casy: 0 3 2 4 1 Pokuty: 8
Kde bolo, tam bolo, mozno niekedy niekto vedel, ze kde, ale uz vsetci zabudli... No, skratka a dobre, bola raz jedna zabudnuta krajina. V tej krajine uz zabudli snad vsetko. Nevedia dokonca, odkial kam ich krajina siaha. Aj to volakedy vedeli, len to uz vsetci zabudli. S najvacsou snahou si kazdy obyvatel teraz pamata jednu priamku. No a na stlpe v hlavnom meste niekto niekedy napisal (Samozrejme uz nik nevie, kto a kedy to napisal a odkial to vedel), ze vsetky priesecniky tychto priamok lezia v zabudnutej krajine. No a teraz by obyvatelia zabudnutej krajiny chceli vediet, ako daleko na vychod ich krajina siaha. A podla moznosti co najrychlejsie, kym nezabudnu, ze to chceli.
V rovine je danych N roznych priamok (kazda dvoma roznymi bodmi, ktore na nej lezia.) Tieto priamky sa pretinaju v niekolkych bodoch. Vasou ulohou je napisat program, ktory najde najpravejsi spomedzi nich, cize ten z nich, ktory ma najvacsiu x-ovu suradnicu. (Ak ich je viac, lubovolny z nich.)
Vstup
(0,1) - (0,3) (2,0) - (2,2) (2,0) - (3,1) (0,3) - (2,2)
Vystup
najpravejsi priesecnik ma suradnice (4,1).
"Tak-ze, tato entitno-relacna, akoze ..." Prednaskovou miestnostou sa niesol monotonny hlas profesora. Kleofas, Zacharias a spolu s nimi asi osemdesiat dalsich studentov zaspavali. "Zacharias, musis mi pomoct! Ked zaspim, hrozne chrapem a vsimne si ma!" "Tak... mam to! Mozme hrat lodicky " navrhol Zacharias. A zacali hrat. Pre tych, co tuto hru nepoznaju: lodicky sa hraju tak, ze jeden hrac rozmiestni svoje lodicky na hracej ploche. Potom sa druhy hrac postupne pyta na policka hracej plochy a dozveda sa, ci tam lodka je alebo nie je.
Ako tak hrali, zrazu sa Zacharias zadival na hraciu plochu a zahlasil: "O kofolu, ze uz najdem vsetky tvoje lodicky a pritom sa najviac raz pomylim!" Kleofas sa tiez zamyslel. Ma vobec sancu, ze vyhra kofolu?
Dane su dve cisla M,N - rozmery hracej plochy. Niekde na hracej ploche sa nachadza presne raz kazda z nasledujucich siedmich lodiciek:
XX X X XX XX X XX XXX XXX XX XX XXX XXXX
Lodicky mozu byt otocene, ale nie preklopene, mozu sa dotykat, nesmu sa prekryvat. Dalej je na vstupe sucasna hracia plocha - M riadkov po N znakoch. + znamena, ze na danom policku je cast nejakej lodky, - je voda a . je este neodkryte policko.
Vasou ulohou je napisat program, ktory vypise na vystup ANO, ak sa v tejto pozicii daju urcite najst vsetky lodicky (cize urcit pre kazde policko hracej plochy, ci je na nom lodicka alebo nie) s tym, ze najviac raz netrafi a NIE v opacnom pripade.
Vstup
10 10 .+..+..... -----+---- -+--+++... ++------.. +---+---.. --++++--.. -----++--+ ------+--+ --------++ ----------
Vystup
ANO
Uz ste niekedy boli v Santolande? A poznate Rumovu jaskynu? Ze nie? No tak to sa musi ihned zmenit. Zoznamte sa:
Zatial najdokonalejsie Santovo dielo, Rumova jaskyna, pozostava z N komor, pre jednoduchost ocislovanych 1 az N. Medzi komorami je mnozstvo uzkych tunelov. Do kazdeho sa na sirku zmesti len jeden zlatokop alebo podobny zivel. Aby nedochadzalo k zrazkam v tuneloch, v kazdom tuneli Santo nakreslil sipku, ktorym smerom sa v nom ma ist. Okrem toho, na zaciatok kazdeho tunela napisal nejake pismeno. No a nakoniec vybral niekolko komor a v kazdej z nich ukryl flasu rumu.
Ak chce niekto hladat v jaskyni flase rumu, dostane pred vstupom do ruky papierik s akousi postupnostou pismen a musi dodrziavat nasledujuce pravidla:
Zlatokopi z celeho okolia bludia bludiskom, avsak flasu rumu najst nevedia. Az prislo Santovi zlatokopov luto. "Tolko sa snazia... Co keby som im to hladanie trochu ulahcil? Nech vedie z kazdej komory na jedno pismeno najviac jeden tunel. To budu vzdy vediet, kade sa pobrat dalej. Len keby som vedel vyrobit taku jaskynu, v ktorej by sa dala flasa rumu najst s tym istym papierikom, ako v tej, co mam. A samozrejme, so ziadnym inym!"
b) Mate danu nasledujucu jaskynu:
N=6, tunely: (1,1,a), (1,1,b), (1,2,a), (2,3,b), (3,3,a), (3,3,b), (3,4,b), (4,5,b), (5,6,a), (6,6,a), (6,6,b), komora s flasou rumu: 6
Vasou ulohou je navrhnut novu jaskynu. Z jednej komory v tejto jaskyni moze na jedno pismenko vychadzat max. 1 tunel. Navyse sa v nej musi dat ziskat flasa rumu iba s tymi papierikmi ako v danej jaskyni a so ziadnymi inymi.
b) Napiste program, ktory nacita pocet komor N, popis tunelov (kazdy tunel je urceny zaciatocnou a koncovou komorou a pismenom napisanym na zaciatku) a zoznam komor, v ktorych su ukryte flase rumu. Od vas sa caka na vystupe popis jaskyne, v ktorej z kazdej komory vychadza na jedno pismenko max. 1 tunel a flasa rumu sa da v nej ziskat len s tymi papierikmi ako v zadanej jaskyni a so ziadnymi inymi. Zdovodnite spravnost vasho algoritmu.