- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 2.kola 18.rocnika KSP-Z
Mile deturence,
Mikulas sa nezadrzatelne blizi, preto by ste si mali nalestit topanky a dat ich do okna. Ak ste boli dobre, rano v nich najdete furu sladkosti. Dajte si pozor, aby ste si nepokazili svoje zaludky.
Riesenia druheho kola nam posielajte do 8. januara 2001. Este predtym, ako nam ich poslete, poproste mamu, aby vam zopla spinkovacom v lavom hornom rohu listy rieseni jednotlivych prikladov.
Zaspis hlad, vyspis dva. Zaspis dva, vyspis styri. ...
- Zaneprazdneny knihovnik
- Zo zapadnutej dedinky
- Zufaly tesar
- Zvlastne zariadenie
- Zeofina v risi fraktalov
1. Zaneprazdneny knihovnik
"Oook!", povedal knihovnik a zamyslene sa zahladel na kopu knih na jeho stole. V kniznici na Neviditelnej univerzite su sice ulozene aj magicke knihy, ale inac je to kniznica ako kazda ina. Studenti prichadzaju, poziciavaju si knihy a co je horsie, aj ich vracaju. Ale pretoze knihovnik nema vtedy cas roznasat ich na miesta v policiach, tak ich len uklada na 2 kopy - magicke vlavo, obycajne vpravo. Obcas sa niektori studenti opytaju, aka kniha je na vrchu tej-ktorej kopy. (Vedeni naivnou vierou, ze najcitanejsie knihy su najlepsie.) Ked sa im zapaci, tak si ju vypytaju a knihovnik im ju poda. No a na konci dna musi chudak knihovnik knihy z kop poroznasat do polic. Pretoze by si chcel dat co najskor banan, pomohol by mu zoznam knih na kopach.
Uloha
Napiste program, ktory bude od knihovnika dostavat prikazy, simulovat obidve kopy knih a ktory na konci dna vypise zoznam knih na obidvoch kopach. Prikazy su:
- Poloz k nazov - Polozi na kopu k (k je 1 alebo 2) knihu nazov.
- Navrchu k - Vypise, aka kniha je na vrchu kopy k
- Zober k - Zoberie z kopy k najvrchnejsiu knihu.
- Koniec - Koniec dna. Program vypise zoznam knih na obidvoch kopach a skonci.
Priklad
> Poloz 1 Prastare primitivne kuzla a cary > Poloz 2 Putnikov sprievodca po Zemeploche > Poloz 1 Principy premien > Poloz 2 Zradca v cechu vrahov > Navrchu 1 Principy premien > Navrchu 2 Zradca v cechu vrahov > Zober 2 > Navrchu 2 Putnikov sprievodca po Zemeploche > Poloz 2 Tajomne zakutia Neviditelnej univerzity > Zober 1 > Zober 1 > Koniec Na prvej kope nie je ziadna kniha Na druhej kope su knihy (odhora nadol) : Tajomne zakutia Neviditelnej univerzity, Putnikov sprievodca po Zemeploche
2. Zo zapadnutej dedinky
Za siedmimi horami, za siedmimi dolinami stala dedina. Tou dedinou sa ozyval krik. To sa Janka s Katkou hadali, ktora z nich je krajsia. "Ja som najkrajsia z celej dediny!", kricala Katka. "Ja som najkrajsia z celeho chotara!", vrieskala Janka. "Nie, ja!", odkricala jej Katka a nahnevane odisla. Urazena Janka tresla dverami (aby sa nepovedalo) a zacala planovat pomstu. Rozhodla sa, ze o Katke rozsiri klebetu. A ze sa ju musi dozvediet kazdy. Klebeta sa siri tak, ze Janka ju porozprava vsetkym ludom, ktorym doveruje. Kazdy z nich ju potom oznami vsetkym tym, ktorym veri a kazdy z nich... Janka teraz smutne sedi nad zoznamom obyvatelov chotara a premysla, ci sa klebetu dozvedia vsetci. Je na vas, aby ste jej s tym pomohli.
Uloha
Napiste program, ktory nacita N - pocet obyvatelov chotara. Pre jednoduchost budeme obyvatelov oznacovat celymi cislami od 1 po N, pricom Janka ma cislo 1. Vas program dalej nacita zoznam usporiadanych dvojic, kto komu veri a vypise, ci sa klebetu dozvie kazdy alebo nie. Pozor, ak napriklad obyvatel a veri obyvatelovi b, neznamena to, ze aj obyvatel b veri obyvatelovi a!Priklad
Vstup
N = 6
Znamosti: 1 3 3 1 1 4 3 5 2 5 3 4 2 6 4 3 2 1 4 6 2 3 5 4 2 4 6 5
Vystup
Nie
Poznamka: Nikto nedoveruje obyvatelovi c. 2.
3. Zufaly tesar
"Nieeee...! Kolko este musim buchat tymto kladivom?", zakrical na celu Rimsku risu tesar Claudius. Cisar mu jednoznacne povedal, ze domov pojde, az ked budu na pamatnej tabuli vsetky vyznamne medzniky Rimskej rise. A tych je veru neurekom... Claudius sa uz tesi domov a chce vediet, kolko uderov este musi spravit.
Rimania zapisuju cislo takto: V poradi od najvacsieho po najmensi napisu znaky, ktore dokopy davaju dany sucet, a to tak, ze vzdy pouziju najvacsi, ktory mozu. Hodnoty znakov su uvedene v tabulke. Napr. 1051 zapisu ako MLI = 1000+50+1. Vynimky z pravidla o poradi su taketo: Namiesto VIIII Rimania napisu IX, namiesto IIII napisu IV, namiesto LXXXX napisu XC, namiesto XXXX napisu XL, namiesto CCCC napisu CD a namiesto DCCCC napisu CM. Takze napr. 1049 napisu ako MXLIX = (M=1000) + (XL=40) + (IX=9).
Uloha
Na kazdu rimsku cislicu je potrebny isty pocet uderov podla tabulky. Zistite, kolko musi Claudius spravit uderov, ked chce vytesat rok, ktory je dany na vstupe v desiatkovej sustave. Mozete predpokladat, ze rok je prirodzene cislo od 1 do 4999.
I = 1 - 1 uder
V = 5 - 2 udery
X = 10 - 2 udery
L = 50 - 2 udery
C = 100 - 2 udery
D = 500 - 3 udery
M = 1000 - 4 udery
Priklad
Vstup
2001
Vystup
9
Poznamka: MMI - 4 udery na kazde M a 1 uder na I.
4. Zvlastne zariadenie
Vedci Neviditelnej univerzity uz maju s vyvojom roznych zvlastnych zariadeni velke skusenosti. Ich pocitac Hex, zalozeny na mravcoch, sa stal svetoznamym. Avsak miniaturizacia pokracuje a tak sa rozhodli vyvinut pocitac, ktoreho hlavnou sucastou budu blchy.
Vysledkom ich doterajsieho snazenia je nasledovne zariadenie. Pozostava z pravidelneho N-uholnika, ktoreho vrcholy su ocislovane od 1 po N a N cvicenych blch, ktore su taktiez ocislovane od 1 po N. V kazdom vrchole N-uholnika je napisana veta naledujuceho typu: "Skoc na vrchol cislo i." Zariadenie ma tu vlastnost, ze pre kazde i z rozsahu od 1 po N existuje prave jeden vrchol, kde je napisane: "Skoc na vrchol cislo i."
Cinnost zariadenia je nasledovna. Na zaciatku vypoctu sa kazda blcha postavi do vrchola s rovnakym cislom, ako ma ona. Potom pri kazdom takte vypoctu (ten je urceny mohutnym uderom na bubon), sa kazda blcha zachova podla prikazu, ktory je napisany vo vrchole, v ktorom stoji.
Vedci neviditelnej univerzity boli svojim dielom nadseni. Po dlhom bubnovani ich vsak zacali trapit pochybnosti, ci vsetko funguje tak, ako ma. Aby skontrolovali cinnost zariadenia, potrebovali by zistit, ako maju byt blchy rozostavene po danom pocte uderov na bubon.
Uloha
Na vstupe je dane N - pocet vrcholov zariadenia a N dvojic celych cisel z rozsahu 1 az N. Dvojica cisel a,b znamena, ze z vrchola a sa ma skakat na vrchol b. Mozte predpokladat, ze dvojice popisuju korektne zariadenie. Dalej je na vstupe dane K - pocet uderov na bubon. Napiste program, ktory vypocita, ako budu po K uderoch rozmiestnene blchy v popisanom zariadeni.
Priklad
Vstup
N=5,K=2
2 5 3 4 1 3 5 2 4 1
Vystup
1.vrchol - blcha c. 4 2.vrchol - blcha c. 2 3.vrchol - blcha c. 1 4.vrchol - blcha c. 3 5.vrchol - blcha c. 5
5. Zeofina v risi fraktalov
Pocas svojej dalsej nostalgickej chvilky zacala Zeofina spominat na svoj pobyt v risi fraktalov. Fraktaly su utvary, ktore sa skladaju z upravenych kopii seba samych. Zeofine sa zachcelo nejaky fraktal si namalovat. Ihned jej jeden prisiel na rozum - Sierpinskeho trojuholnik.
Sierpinskeho trojuholnik je rovnostranny trojuholnik, do ktoreho su vlozene tri dalsie Sierpinskeho trojuholniky s polovicnou dlzkou strany. Tieto trojuholniky sa dotykaju rohmi a dve z ich stran su casti stran povodneho trojuholnika, tak ako na obrazku.
 Sierpinskeho trojuholnik |
 radu 1 |
 radu 2 |
 radu 3 |
 radu 4 |
 radu 5 |
Zeofina sa rozhodla uz-uz zacat kreslit, ked si uvedomila ze taky Sierpinskeho trojuholnik je vlastne utvar tvoreny nekonecnym poctom trojuhlnikov. A ona tolko kreslit nebude. Preto sa rozhodla nakreslit iba zjednodusenu verziu, a to Sierpinskeho trojuholnik radu N. Sierpinskeho trojuholnik radu 1 je vlastne obycajny trojuholnik. Sierpinskeho trojuholnik radu N sa sklada z troch Sierpinskeho trojuholnikov radu N-1. Z tych klukatych ciar ju uz stihla rozboliet hlava, a preto jej pomozte najst postup, ako na to.
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
Uloha
Napiste program, ktory nacita N - rad Sierpinskeho trojuholnika a vypise postupnost povelov pre Zeofinu, ktorymi takyto trojuholnik nakresli.
Poznamka
V ramci testovania vasho programu vam odporucame nielen vypisat postupnost povelov, ale aj nakreslit vysledny obrazok. (Na to mozete pouzit napriklad unit graph3 v Borland Pascale.)
(c) 2000 webmaster
