- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 2. kola
Mili nasi riesitelia,
mozno si to este ani neuvedomujete, ale coskoro tu budu Vianoce. Aj my sme Vam chceli pripravit nejaky darcek a tak ho tu mate --- zadania 2. kola. Svoje riesenia posielajte na horeuvedenu adresu do 8. januara 1996.
A este mala reklama: mame konkurenciu! Vznikol PROKOS --- Zilinsky korespondencny seminar z programovania (Mgr. Marian Rendek, KI FR VSDS, Velky Diel, 010 26 Zilina). Tymto mu chceme zapriat vela stastia a riesitelov. No a ked uz o inych seminaroch, tak tu je adresa dalsieho: KSP KSVI MFF UK, Malostranske namesti 25, 118 00 Praha 1.
Ti, co minule zadudli, nezabudnite na obalku pripisat KSP. A takisto (ak ste to este neurobili) nezabudnite poslat vyplneny evidencny listok (najdete ho v propoziciach).
Na Novy rok o slepaci krok!
1. O kralovstvach na Kiribati
Kiribatske deti sa strasne radi hravaju na kralov a kralovne --- niet divu, ved kiribatske suostrovie ma tolko ostrovov, ze kazdy obyvatel moze vladnut aspon jednemu.
Raz sa im dostala do ruk mapa celeho suostrovia. Kazdy ostrov bol zobrazeny jednou bodkou. Deti sa zacali hrat hru, pri ktorej si kazdy vybral kralovstvo obdlznikoveho tvaru, ktoremu by chcel vladnut. Nezalezalo vsak na rozlohe kralovstva, ale na pocte ostrovov --- ten kto ich ma najviac, stane sa Najmocnejso-Najhrozostrasnejso-Najsilnejsim panovnikom.
Uloha: Napiste program, ktory nacita suradnice ostrovov na mape (realne cisla). Dalej nacita kralovstva, pricom kralovstvo je dane suradnicami laveho horneho a praveho dolneho rohu (cele cisla v rozsahu 0---100) obdlznika a pre kazde kralovstvo vypise pocet ostrovov, ktore sa v nom nachadzaju.
2. Brutus a Frutus v kniznici
Brutus a Frutus po navsteve u zubara navstivili aj kniznicu. Vybrali si knihu ``Zbierka uloh KSP'' a zacali v nej listovat. Ked si konecne zo zbierky vybrali ten najzaujimavejsi priklad a chceli sa pozriet na jeho vzorove riesenie, zistili, ze vzorove riesenie je z knizky vytrhnute.
Uloha: Na vstupe je cislo N a N celych cisel v rozsahu 1...N^2. Utriedte tieto cisla.
Poznamka: O(n log n) nie je ani zdaleka najlepsie riesenie.
3. Banto a dostavniky
Banto chce navstivit staru mamu Prabantovku, ktora byva az hen v Nalomenej Trieske. Preto musi vediet, ako chodia v Nalomenej Trieske dostavniky. Prabantovka nevie, ktory dostavnik kedy a kam chodi, ale vzdy, ked jej prehrkoce nejaky pod oknami, velmi ju to rozrusi, lebo dostavniky robia velky hluk. Vecer si Prabantovka vsetky vzrusujuce veci (teda aj prechod dostavnika) zapise do dennika. Chudak Banto by aspon chcel vediet, kolko roznych liniek chodi cez Nalomenu Triesku. Preto poziadal Prabantovku, aby mu poslala vypis z dennika. Teraz sedi nad listom od starej mamy a nevie si rady.
Uloha: Napiste program, ktory nacita obsah dennika Prabantovky a vypise, kolko najmenej dostavnikovych liniek chodi cez Nalomenu Triesku.
Vypis z dennika Prabantovky obsahuje zaciatok sledovaneho obdobia, pocet dostavnikov, ktore za sledovane obdobie presli popred Prabantovkine okna a dalej pre kazdy dostavnik den, kedy presiel popod okna. Prabantovka zasadne nepise datumy, ale pocet dni od jej narodenia. Sledovane obdobie trva 60 dni. Zapisy su chronologicky usporiadane.
Dostavnikova linka sa vyznacuje tym, ze dostavniky chodia v pravidelnych intervaloch pocas celeho sledovaneho obdobia. Kazda linka prejde popod Prabantovkine okna pocas sledovaneho obdobia aspon dvakrat. Mozete predpokladat, ze cez Nalomena Triesku nechodi viac ako 17 liniek a ze za sledovane obdobie nepreslo popod Prabantovkine okna viac ako 300 dostavnikov.
Priklad:
Vstup:
25500 17 25500 25503 25505 25513 25513 25515 25521 25526 25527 25529 25537 25539 25539 25545 25551 25552 25553Vystup: 3 linky
(s intervalmi 13,12 a 8 dni, prvy dostavnik z linky ide v den 25500, 25503 a 25505)
4. O vikingskom cestovatelovi
V roku 1101 sa vikingsky cestovatel Uwe Pisgarson doplavil az k brehom Juznej Ameriky. Len co vystupil zo svojej lode, zajali ho domorodci a chystali sa ho obetovat (t.j. obedovat). Po dlhom proseni ich Uwe presvedcil, aby mu dali este jednu sancu. Nacelnik ho zaviedol do obrovskej miestnosti, v ktorej bol na stene velky, tazky kamenny kotuc s kolikmi po obvode pripominajuci lodne kormidlo. Kotuc sa dal otacat oboma smermi. Najspodnejsi z kolikov bol natrety cervenou farbou. Na niektorych kolikoch boli pripnute zlate disky, zvysne disky lezali na zemi. ``Pozri !'' povedal nacelnik Uwemu a ukazal na mozaiku na protilahlej stene. Znazornovala rovnaky kotuc ako v miestnosti, cerveny kolik opat smeroval nadol, iba disky boli inak rozmiestnene. ``Ak do vychodu Slnka budu na obidvoch stenach rovnake kotuce, si volny. Inak.''
Pisgarson si pozornejsie obzrel kotuc. Zistil, ze ho vladze otocit o jedno miesto v oboch smeroch, alebo pripnut (resp. odobrat) disk na spodny kolik (na ine koliky nedociahol).
Len co osamel, dal sa do prace. Zacal rychlo otacat kotuc, pripinat a odoberat disky. Kotuc bol vsak velmi tazky, a tak sa Uwe rychlo unavil. Nad ranom od vysilenia odpadol a ulohu nesplnil.
Uloha: Napiste program, ktory zachrani uboheho Uwe Pisgarsona pred krutou smrtou. Vas program nacita pocet kolikov N, potom reprezentaciu kotuca t.j. postupnost nul a jednotiek (koliky bez disku a koliky s diskom) pocnuc cervenym kolikom v smere hodinovych ruciciek a nakoniec reprezentaciu mozaiky (rovnakym sposobom ako kotuc).
Vystup bude postupnost pismen L,P,V (otocit o jedno miesto v smere hod. ruciciek, proti smeru hod. ruciciek, vymena disku na spodnom koliku), ktora zabezpeci, ze Uwe splni ulohu a nezomrie od unavy (t.j. dlzka vystupnej postupnosti ma byt minimalna).
Poznamka: Kotuc je velmi tazky a Uwe zomrie velmi rychlo.
Poznamka 2: Diskov je k dispozicii dostatocny pocet.
5. O politikoch
Politici to vobec nemaju jednoduche. Cele dni musia vysedavat na schodzach parlamentu, zasadnutiach roznych komisii a vyborov, podchvilou sa poriada nejaka tlacova konferencia, alebo sa novinari snazia ziskat interview. Ale to vsetko by sa este dalo vydrzat. Najhorsie je, ze taky politik musi velmi casto pisat politicke prejavy. Je to horsie ako domace ulohy zo slohu.
Velmi dolezite je, aby mal prejav pozadovanu dlzku, pricom dlzka prejavu sa meria v pocte riadkov. Vsetky riadky (okrem posledneho) obsahuju 60 pismen. Takisto by mal byt prejav zakazdym iny --- ak by politik vzdy pouzil ten isty prejav, hrozi, ze si to za nejaky cas niekto vsimne (je vsak velmi pravdepodobne, ze by to trvalo aspon jedno volebne obdobie).
Uloha: Napiste program, ktory na vstupe dostane predpisany pocet riadkov politickeho prejavu a vypise co najposobivejsi politicky prejav predpisanej dlzky. Vo svojom prejave mozete pouzit nasledovne symboly: < DP> --- dramaticka pauza, :-} --- podmanivy usmev, 8-( --- zdrave rozhorcenie, < NSVPS> --- nadsene suhlasne vykriky z poslaneckej snemovne.
Poznamky: K rieseniu pripojte priklady vystupu aspon pre 3, 10 a 50 riadkov v dvoch kopiach.
(C) 1995, Organizers of the CSP
