- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 3. kola
Ahoj riesitel,
dufame, ze Ta priklady KSP-cka zaujali a uz netrpezlivo ocakavas dalsiu, tretiu a zaroven poslednu seriu. Urcite o nas rozpravas vsetkym kamaratom a ten mesiac medzi seriami trpnes nedockavostou po novych problemoch, ktore by si mohol(-la) skolit. Nebudeme Ta preto viac napinat, len Ti poprajeme prijemne jarne prazdniny a veselu Velku noc popri rieseni tretej serie KSP kategorie Z. Plody Tvojej cinorodej prace nam bez obav posli do 14. aprila 1998. A, mimochodom, peknej pohladnici z lyzovacky alebo hocikial inakadial sa vzdy potesime.
Pravidelne si cistite topanky !
KSPaci
1. Zmagoreny marsochod
Pisal sa rok 2020, vyskumy povrchu Marsu boli v plnom prude, ked do ustredia KSP (Kontrola Skumania Planet) prisla sprava o zvlastnom spravani isteho marsochodu Z-10. Z-10 sa pri navrate podarilo dostat na nahornu plosinu, na ktorej je zakladna. Na tejto plosine sa mu vsak pokazili niektore motoricke obvody, a preto sa dokaze hybat iba smerom na juh a vychod o nasobky dlzky 100m (nedokaze sa totiz otacat a opacny nahon kolies bol zablokovany). Nastastie sa zakladna nachadza juhovychodne od Z-10. Medzi zakladnou a Z-10 su vsak rozlicne prekazky (virive magneticke polia, ionove mracna, vymole, priepasti), cez ktore nemozno prejst. Takisto sa od Z-10 chce, aby cestou na zakladnu vykonal co najviac prace, ktora bola pren planovana.
Uloha: Na vstupe je cislo N - rozmer mapy (N<=100) a matica N x N celych cisel, ktore predstavuju mapu nahornej plosiny. Jedno policko matice reprezentuje stvorec terenu s rozmerom 100 x 100 metrov. Policka so zapornou hodnotou predstavuju prekazky, policka s kladnou hodnotou su tie, na ktorych treba nieco spravit. Ostatne policka maju hodnotu 0. Dalej su na vstupe suradnice (R,S) stvorceka mapy, na ktorom stoji Z-10 (R je riadok, S je stlpec). Zakladna sa nachadza na pravom dolnom policku mapy (toto policko ma suradnice (N,N)).
Najdite taku cestu, po ktorej moze Z-10 prejst (t.j. neprechadza cez ziadnu prekazku) a na ktorej lezi najvacsi mozny pocet miest, kde treba nieco vykonat. Cesta je postupnost policok mapy zacinajuca v (X,Y), konciaca v (N,N), pricom kazde policko je bud priamo pod predchadzajucim alebo napravo od neho. Ak existuje takychto ciest viac, vypiste lubovolnu z nich, ak neexistuje ziadna, vypiste prislusnu spravu.
Priklad:
Vstup:
N=3, R=1, S=1
Mapa:
0 1 1 0 -1 -1 0 3 0
Vystup:
Najlepsia cesta:
(1,1), (2,1), (3,1), (3,2), (3,3)
2. Zeofinine veze
Po mnohych nastrahach sa Zeofine podarilo takmer nemozne - vratila sa na rodne Galapagy. Predtym vsak presla hodny kus sveta. A vsetky uzovky, volavky, ba aj korytnacie druzky sa zacali Zeofiny vypytovat, ako v tom velkom svete bolo. Zaujimali sa najma o Europu. Tu Zeofinu obzvlast zaujali hrady a zamky. Chcela im nejake nakreslit. Zistila vsak, ze ak chce, aby pochopili, ako hrady vyzeraju, musi ich najskor oboznamit s niecim jednoduchsim - napriklad s vezami.
Veza stupna 1, resp. 2 a velkosti d je na obr. 1, resp. obr. 2. Vezu stupna s+1, s>1 a velkosti d dostaneme z vezi nizsich stupnov nasledujucim sposobom. Najskor nakreslime zvislu ciaru dlzky d, na nu nadvazuje veza stupna s a velkosti d/2. Za touto podvezou nasleduje skupinka veziciek, ktore by sme dostali, ak by sme vezu stupna s prevratili horeznacky, za touto skupinkou je opat veza stupna s, za ktorou sa este dokresli zvisla ciara s dlzkou d.
Uloha: Napiste program, ktory pre zadane s a d vypise postupnost prikazov pre Zeofinu tak, aby nakreslila vezu stupna s a velkosti d. Zeofina pozna prikazy DOPREDU a (posunutie v smere aktualneho natocenia o dlzku a; zanechava pri tom za sebou ciaru), VLAVO u a VPRAVO u (zmena aktualneho natocenia o uhol u).
3. Znak krasy
Kde bolo, tam bolo, za siedmimi horami a siedmimi dolami zil raz jeden kral a ten kral mal jednu-jedinku dceru. A ta bola taka pekna, aka bola hlupa. A veru, vacsiu spatu nepoznalo ani Zrkadielko zo susedneho Snehulienkinho kralovstva. Ani hlupy Jano by si ju nevzal za zenu, hoc aj s pol kralovstvom. Ale vsetci si ju vazili pre jej mudrost a zdalo sa, ze princeznej krasa nechyba. Avsak len do dna, ked sa jej kralovsky otec rozhodol spravit z nej svoju nastupkynu, ked uz mu Boh nepozehnal syna a zat bol v nedohladne. Princezna bola sice bystra a mudra, ale ako moze svojim vzhladom reprezentovat vlastnu krajinu v zahranici? A tak princezna putovala od jedneho plastickeho chirurga k druhemu, z jedneho salona krasy do druheho, ale vysledok nebol omnoho lepsi. Jedina nadej bola v starej dobrej carodejnici Kirke. Kirka usadila princeznu do zapraseneho kresla a cosi si mumlala popod nos, zatial co v kotliku bublala tajomna tekutina. A cuduj sa svete, kuzlo sa podarilo! Z vonavych par vystupujucich z kotlika sa vyformoval akysi obrazec a lahko ako pavucinka pristal na novych Kirkinych zaclonach. Bol to univerzalny znak krasy. Skor nez odleti, princezna si ho musi odkreslit na papier. Nesmie vsak zdvihnut pero z papiera skor, ako bude cely obrazec nakresleny. Princezna to samozrejme zvladne, ale skuste presvedcit Kirku, ze v tom nie su ziadne cary, a mozno vam aj uveri.
Uloha: Vstupom vasho programu bude popis znaku. Znak krasy sa sklada z niekolkych uzlov, pricom medzi niektorymi z nich vedu ciary. Prvy riadok vstupu obsahuje cisla n a m, kde n je pocet uzlov a m je pocet ciar. Uzly su ocislovane cislami 1,2,...,n. Potom nasleduje m dvojic cisel uzlov, kazda dvojica obsahuje koncove body jednej ciary. Vas program ma vypisat postupnost cisel uzlov udavajucu, ako sa bude dany obrazec kreslit. Kazda ciara musi byt vykreslena prave raz.
Priklad:
Vstup:
5 8
1 2
1 4
1 3
3 5
5 4
2 3
2 4
3 4
Vystup:
1 3 5 4 2 3 4 1
4. Zufaly Santo
Santo sa otocil a uvidel, ze sa za nim objavil stol plny jedla. Podisiel k nemu, naciahol sa a CRRRRRRRRRRRN. Santova ruka vyletela a zmietla budik zo stola. Ked sa konecne vyhrabal spod perin, zbadal na zemi rozkotulane kolieska. Vzdychol, ale kedze Santo je sikovny chlapik, nakoniec sa mu podarilo budik opravit. No ked ho natiahol, zistil, ze sa rucicky tocia opacnym smerom. Pokusal sa ho znovu opravit, ale uplne sa poplietol, ktorym smerom sa ma ktore koliesko tocit. Teraz skusa otacat roznymi kolieskami a pozera, ktore sa kam toci.
Uloha: Je dany pocet koliesok n, suradnice stredov a polomery vsetkych koliesok a smer otacania prveho kolieska zo vstupu. Ziadne dve kolieska sa v rovine nepretinaju, niektore dvojice sa vsak mozu dotykat. Ak sa dve kolieska dotykaju, musia sa otacat navzajom roznymi smermi. Majme dve dotykajuce sa kolieska K1 a K2. Nech koliesko K1 ma polomer r1 a koliesko K2 polomer r2. Ich rychlosti otacania (fyzik by povedal uhlove rychlosti) omega1 resp. omega2 musia byt v opacnom pomere ako polomery, t.j. omega1/omega2 = r2/r1. Rychlost otacania prveho kolieska je 1 otacka za minutu. Ak nie je mozne tieto podmienky splnit, budik sa zasekne. Naopak, moze sa stat, ze nejaka skupinka koliesok nema ziadne spojenie s kolieskom 1 a preto stoji.
Zistite, ktorym smerom a akou rychlostou sa otaca kazde z koliesok. Ak sa budik zasekne, vypiste o tom spravu Budik sa zasekol. Kolieska, ktore nie su v spojeni s prvym kolieskom maju nulovu rychlost otacania. Ak taketo kolieska existuju, vypiste o tom spravu Budik ma nepohanane kolieska.
Poznamka: Polomery a stredy su zadavane ako realne cisla. Pocitajte s tym, ze presnost vstupov aj vypoctov bude ovplyvnena zaokruhlovacimi chybami (pozor na porovnanie).
Priklad:
Vystup pre budik vlavo:
Rychlost Smer ------------------------------- K1 1 zaporny K2 1.828 zaporny K3 1.828 kladny K4 1.828 kladny K5 1.828 zaporny
Vystup pre budik vpravo:
Budik sa zasekol
5. Zakryvanie koberca
Na Kiribati vladne zhon. Coskoro do ich krajiny pride na navstevu nacelnik susedneho suostrovia a Kiribatcania chystaju slavnostne privitanie. Volakde zohnali dokonca aj dlhocizny cerveny koberec a rozhodli sa rozprestriet ho od letiska az do stredu ich hlavnej osady. Ako ho tak rozprestieraju, zrazu zistili, ze na mnohych miestach je koberec prehryzeny od moli!
Aby v hanbe nezostali, musia s tym nieco spravit. V mnohych kiribatskych domacnostiach pouzivaju male cervene koberceky, ktore su sice rovnako siroke, ako dlhocizny koberec, ale dlhe su iba jeden meter. Niekoho napadlo, ze by sa tymito kobercekmi dali zakryt useky koberca, ktore su prehryzene od moli. Chceli by vsak pouzit co najmenej kobercekov, aby v domacnostiach zbytocne nechybali.
Uloha: Dana je dlzka koberca d, pocet poskodenych usekov koberca n a pre kazdy poskodeny usek su dane vzdialenosti jeho zaciatku a konca od letiska (v metroch). Vypiste najmensi pocet kobercekov, aky staci na zakrytie, ak kazdy poskodeny usek musi byt cely zakryty kobercekmi, koberceky nemozno strihat (po odchode navstevy ich treba vratit povodnym majitelom), ale mozu sa navzajom prekryvat. Dalej vypiste, ako treba jednotlive koberceky poukladat, aby sa zakryli vsetky poskodene useky.
Dolezitou sucastou riesenia je dokaz, ze vas algoritmus je spravny, t.j. ze vzdy pozakryva diery pomocou najmensieho mozneho poctu kobercekov.
Priklad:
Vstup:
d=10, n=3
Poskodene useky:
Zaciatok Koniec 1.2 1.3 5.4 6.5 1.95 2.1
Vystup:
Stacia 3 koberceky.
Rozmiestnenie kobercekov:
Zaciatok Koniec 1.15 2.15 5.4 6.4 5.4 6.5
1998, Organizers of the CSP
