- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 1.kola 18.rocnika KSP-Z
Mily(a) nas(a) riesitel(ka),
riesenia prveho kola nam posli do 6. novembra 2000. Predtym, ako nam ich posles, nezabudni si precitat propozicie. Dozvies sa z nich par veci, ktore by ta mohli zaujimat. Spolu s rieseniami nam posli aj vyplneny evidencny listok a znamky v celkovej hodnote 15,- Sk.
KSPaci
- Zo zivota informacnej kancelarie
- Zaoceanske Krizniky, Skunery a Plavby
- Zabudnute cisla
- Zauzleni studenti
- Zeofina sa vracia
1. Zo zivota informacnej kancelarie
V meste Kocurkovo otvorili novu informacnu kancelariu. Kancelaria to bola pekna, otvorena NON-STOP. A kedze vsetkych navstevnikov pri prichode ponukali poharom chladeneho piva, coskoro ju zacalo navstevovat mnozstvo ludi. Bolo ich tak vela, ze sa pred kancelariou utvoril dlhy rad.
Aby ludia nemuseli stat v rade, rozhodol sa v kancelarii nainstalovat rezervacny system. Kazdy obcan, ktory sa chce v kancelarii informovat, zada do pocitaca umiestneneho pri vchode svoje cislo (kazdy Kocurkovcan ma svoje jednoznacne cislo) a cislo okienka, ku ktoremu sa chce ist informovat (v kancelarii maju K okienok ocislovanych 1 az K a kazde z nich poskytuje iny druh informacii), pocitac ho zaradi a obcan sa moze ist poprechadzat do nedalekeho parku. V okamihu, ked sa obcan dostane na rad (t.j. po vybaveni vsetkych obcanov ktori prisli pred nim a cakali na to iste okienko) sa na velkej svetelnej tabuli nad vchodom rozsvieti jeho cislo a obcan sa moze dostavit k okienku. Vasou ulohou je pomoct riaditelovi zrealizovat tento ambiciozny projekt.
Uloha
Napiste program, ktory bude riadit privolavanie cakajucich pomocou svetelnej tabule. Vas program na zaciatku nacita pocet okienok K. Potom bude na vstupe dostavat spravy tvaru PRISIEL x o a UVOLNILO SA o. Prvy druh spravy oznamuje, ze obcan cislo x prisiel do kancelarie a chce ist k okienku o. Druhy druh oznamuje, ze od okienka o prave odisiel klient, cim sa toto okienko uvolnilo. Vas program ma vzdy, ked sa uvolni okienko a niekto nanho caka, alebo niektore okienko je volne a pride obcan, ktory sa chce pri nom informovat, vypisat cislo obcana, ktory je pri tomto okienku prvy na rade. Snazte sa, aby vas program reagoval dostatocne rychlo, aby nedochadzalo k zbytocnym zdrzaniam. Kedze kancelaria funguje non-stop, vas program by mal tiez bezat bez prerusenia.
Priklad
Vstup: PRISIEL 20 2 Vystup: obcan 20 k okienku 2 Vstup: PRISIEL 11 2 Vstup: PRISIEL 15 1 Vystup: obcan 15 k okienku 1 Vstup: UVOLNILO SA 2 Vystup: obcan 11 k okienku 2 Vstup: UVOLNILO SA 2 Vstup: PRISIEL 99 2 Vystup: obcan 99 k okienku 2 Vstup: UVOLNILO SA 1
2. Zaoceanske Krizniky, Skunery a Plavby
Pedro Primorsky, generalny riaditel spolocnosti Zaoceanske Krizniky, Skunery a Plavby, sa rozhodol zveladit pristavy spolocnosti a ziskat tym viac zakaznikov. Penazi je ale malo, preto chce Pedro vybrat iba najfrekventovanejsi pristav. To ale nie je jednoduche, pretoze jedine zaznamy, ktore v Z KSP maju, su zoznamy liniek, na ktorych prepravuju cestujucich. Vie sa, ze vsetky linky su obojsmerne a ze medzi kazdymi dvoma pristavmi premava nanajvys jedna linka. Kedze vsak niektori uradnici su nedosledni, moze sa v zozname jedna linka vyskytnut aj viackrat.
Uloha
Napiste program, ktory nacita pocet pristavov N a zoznam dvojic pristavov, medzi ktorymi premava lod a vypise cislo najfrekventovanejsieho pristavu, cize pristavu, z ktoreho vychadza najviac liniek. Ak je takychto pristavov viac, vypiste vsetky.
Priklad
Vstup
N=5 Linky: 1-3, 2-1, 3-1, 3-1, 3-2, 4-2, 5-3
Vystup
Pristavy, z ktorych vychadza najviac liniek: 2, 3.
3. Zabudnute cisla
Zil raz jeden matematik, strasny zvedavec to bol. A aj sa volal Zvedavec, lebo tak sa volal jeho otec, dedko, pradedko, ... No a ako sa na spravneho zvedavca patri, chcel preskumat vsetko, co sa mu dostalo pod ruky. A tak necudo, ze sa usilovnym prezeranim kniznic docital aj o "minus dvojkovej sustave". Hned sa mu tato sustava zapacila, no vzapati sa zhacil: a ako to vobec moze fungovat?
Uloha
Zvedavca by urcite velmi potesilo, ak by ste mu napisali program, ktory by mu prevadzal cisla z desiatkovej sustavy do minus dvojkovej a naopak. Minus dvojkova sustava je taka, ze pouzivane cifry su 0 a 1 a zakladom sustavy je cislo -2; vezmime si napriklad take cislo 100110, jeho hodnota (v desiatkovej sustave) je 1*(-2)5 + 0*(-2)4 + 0*(-2)3 + 1* (-2)2 + 1*(-2)1 + 0*(-2)0 = -30. Vo vseobecnosti, nech xn-1xn-2 ... x2x1x0 su cifry cisla v minus-dvojkovej sustave, potom jeho hodnota bude xn-1*(-2)n-1 + xn-2*(-2)n-2 + ... + x2*(-2)2 + x1*(-2)1 + x0*(-2)0.
Poznamka
Pokuste sa dokazat, ze kazde cele cislo sa da zapisat v minus dvojkovej sustave prave jednym sposobom.
Priklad
Vstup 1
7 (sustava: 10)
Vystup 1
11011 (sustava: -2)
Vstup 2
110101 (sustava: -2)
Vystup 2
-11 (sustava: 10)
4. Zauzleni studenti
Studenti istej nemenovanej fakulty maju kopu divnych napadov. Nedavno ich napadla takato hra. Zaviazali si oci a nahodne sa pochytali za ruky, pricom kazdy z nich nasmatral pravou rukou nejaku lavu ruku a pevne sa jej chytil. Teraz by sa chceli rozuzlit. Chvilu sa o to neuspesne pokusali, potom to vzdali a zacali rozmyslat. Nakoniec prisli na to, ze by sa hadam aj vedeli rozmotat, no najprv musia vediet, kolko kruhov vlastne tvoria.
Uloha
Na vstupe je dany pocet studentov N a N cisel, pricom i-te cislo v poradi je cislo studenta, ktoreho sa drzi i-ty student pravou rukou. Napiste program, ktory vypise pocet kruhov v spletenci, ktory studenti vytvorili. Kruh je pritom kazda postupnost studentov (dlzky aspon 1) s1,s2,...,sk taka, ze student s1 drzi pravou rukou studenta s2, s2 drzi s3... sk drzi s1.
Priklad
Vstup
4 1 3 4 2
Vystup
2(Su to kruhy 1 a 3,4,2)
5. Zeofina sa vracia
Zeofina je korytnacka. Zoznamte sa. - Ahoj, ja som riesitel KSP. - Tesi ma, Zeofina - povedala korytnacka a dodala: - Ja som v KSP stara znama. Uz pred tromi rokmi som sa vyskytovala v zadaniach KSP. Lenze na to sa ty, mily riesitel, iste nebudes pamatat (Nebodaj sa pamatas? Uz vtedy si riesil/a nas seminar? A to sa nehanbis riesit priklady kategorie Z? Uz aj hybaj riesit ostru kategoriu! :-))... - Zeofina zacala spominat. Hovorila o svojich cestach svetom, o svojej mladosti, o nadhernych nociach na Galapagach a - ach, tie hviezdy! Co by za to Zeofina dala, keby este niekedy v zivote mohla zazriet galapagske hviezdy...
Uloha
Pomozte Zeofine aspon tym, ze jej napisete program, ktory jej povie, ako si moze nejaku hviezdu nakreslit. Viete pritom, ze galapagska n-cipa hviezda (n>= 3) ma n cipov vo vrcholoch pravidelneho n-uholnika. Z kazdeho cipu vedu dve usecky do "takmer protilahlych" cipov. Aby ste mali predstavu, ako taka hviezda vyzera, Zeofina vam doniesla ukazat niekolko z nich na obrazku:
 n=3 |
 n=4 |
 n=5 |
 n=6 |
 n=7 |
 n=8 |
Ked chce Zeofina kreslit, namoci si chvostik do atramentu, postavi sa doprostred velkeho cisteho papiera a zacne sa po nom presuvat. Ak ma chvostik spusteny, zanechava za sebou ciaru, ak ho ma zdvihnuty, presuva sa len tak. Aby sa pri kresleni nepomylila, dopredu sa nauci postupnost povelov tvaru
- dopredu k - pohni sa k krokov dopredu (k je realne),
- dolava u - otoc sa o u stupnov dolava,
- doprava u - otoc sa o u stupnov doprava,
- zdvihni - zdvihni chvostik a
- poloz - poloz chvostik na papier
Vas program by teda mal nacitat cislo n a vypisat postupnost povelov, pomocou ktorych bude Zeofina schopna nakreslit n-cipu galapagsku hviezdu.
Poznamka
Pokuste sa zminimalizovat pocet pouziti povelov poloz a zdvihni. Taktiez by korytnacku Zeofinu potesilo, keby sa pri kresleni hviezdy co najmenej nachodila.
Priklad
Vstup
n=3
Vystup
poloz dopredu 10 dolava 120 dopredu 10 dolava 120 dopredu 10
(c) 27. september 2000, webmaster
