- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 2.kola 18.rocnika KSP
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.
1. O bojovej sekere
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.
Uloha
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.
Priklad
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.
2. O byrokracii v Bratislave
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.
Uloha
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.
Priklad
Vstup
N=5 Terminy: 0 3 2 1 1 Pokuty: 100 10 1 8 9
Vystup
Casy: 0 3 2 4 1 Pokuty: 8
3. O zabudnutej krajine
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.
Uloha
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.)
Priklad
Vstup
(0,1) - (0,3) (2,0) - (2,2) (2,0) - (3,1) (0,3) - (2,2)
Vystup
najpravejsi priesecnik ma suradnice (4,1).
4. O nudnej prednaske
"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?
Uloha
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.
Priklad
Vstup
10 10 .+..+..... -----+---- -+--+++... ++------.. +---+---.. --++++--.. -----++--+ ------+--+ --------++ ----------
Vystup
ANO
5. O Santolande II
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:
- V komore c. 1 svoju put zacne.
- Predpisane smery v tuneloch dodrziavat bude.
- Len do takeho tunela vojde, na zaciatku ktoreho rovnake pismeno ako prve nevyskrtnute pismeno na papieriku je. Po prejdeni tunela toto pismeno z papiera vyskrtnut sa musi.
- Ak ziadny tunel z komory na pozadovane pismeno nevedie, zlatokop sa s hanbou z jaskyne domov pobrat musi.
- Komu uz ziadne pismeno na papieriku nezvysilo, v komore, v ktorej sa prave nachadza, flasu rumu vyhladat moze."
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!"
Uloha
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.
(c) 2000 webmaster
