- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 1. kola
Mili nasi riesitelia,
vitame Vas v novom rocniku Korespondencneho seminara z programovania - kategoria Z. Na uvod niekolko upozorneni: vyplnte evidencny listok, precitajte si propozicie, diskety nam neposielajte, s rieseniami nam poslite dvoj a trojkorunove znamky v celkovej hodnote 10.- Sk.
Dost uz bolo! Hajde riesit! Prajeme Vam vela stastia pri rieseni uloh a tesime sa na pripadne stretnutie na sustredeni. Riesenia nam posielajte do 17. novembra 1997.
Nezabudnite si umyt usi!
1. Zorov znak
Zoro pomstitel daval velmi charakteristickym sposobom najavo svoju pritomnost. Dnes by sme povedali, ze si potrpi na image. Po kazdom jeho (vy)cine bolo podla pismena Z, nacrtnuteho tromi rychlymi tahmi spickou kordu na stenu alebo iny podklad (tvare jeho nepriatelov nevynimajuc) vidiet, s kym ma clovek tu cest. Historicky ustav po velkom usili nazhromazdil mnozstvo fotografii stien budov, v ktorych predpokladali, ze by sa Zoro mohol vyskytovat. Fotografii je vsak strasne vela, ich prezeranie by trvalo strasne dlho. Pomozte pracovnikom Historickeho ustavu a napiste program, ktory zisti, kolko znakov Z je na fotografii.
Uloha: Fotografia je obdlznikove pole (MxN) nul a jednotiek, Z sa sklada z dvoch vodorovnych a jednej sikmej usecky, zvierajucej s oboma osami uhol 45 stupnov. Kazda z useciek je dlzky aspon 3. Vsetky tri usecky mozu byt lubovolne dlhe, avsak sikma usecka musi pretinat obe vodorovne. Predpokladajte, ze ziadne Z nesusedi so ziadnym inym tmavym bodom. Napiste program, ktory zisti, kolko takychto pismen Z sa nachadza v tomto poli.
Priklad:
Vstup:
000000000001000000010 111111111111100000100 000000000100011111110 111001001001000010000 010000010001000100000 000111111100011111000
Vystup:
Na stene su dva znaky Z.
2. Zeofina spomina
Korytnacka Zeofina to nemala lahke. Jej sestra Zofka sa stala slavnou pre svoje matematicke vedomosti. Zeofinu vsak este v detstve uniesli z rodnych Galapag vedci, aby preskumali jej zvlastne schopnosti. Po strastiplnych rokoch sa jej konecne podarilo utiect z laboratoria v Kahire. Utekala, utekala (ako to len korytnacky dokazu) a ani nevedela ako sa dostala na pust, kde ju zastihla piesocna burka.
Ked sa burka utisila, uvidela okolo seba holu plan. Urobila tri kroky a zistila, ze za sebou zanechava v piesku stopu. Takto si zacala do piesku kreslit obrazky. I zacnelo sa jej za domovom, a tak sa rozhodla, ze nakresli stromy, ake rastu na Galapagach.
Stromy
na Galapagach predovsedkym nemaju listy a su sumerne podla osi kmena. Pre
kazdy druh je specificka dlzka kmena d a uhol rozovretia konarov
u. Cim je strom starsi, tym je kosatejsi. Jednorocny strom tvori
vlastne iba jeho kmen. Ak ma strom n rokov (n>1), tak
na konci jeho kmena vybiehaju dva konare. Jeden vlavo pod uhlom u/2
a druhy vpravo pod uhlom u/2. Kazdy z tychto konarov sa moze dalej
kosatit a vyzeraju presne ako stromy s vekom n-1, polovicnou dlzkou
kmena a rovnakym uhlom rozovretia konarov.
Uloha: Napiste program, ktory povie korytnacke Zeofine, ako ma nakreslit strom. Vas program nacita kladne cele cisla n, u, d a napise seriu pokynov pre korytnacku Zeofinu. Korytnacka vie reagovat na tieto pokyny: Dopredu a - posunie sa v smere svojho natocenia o dlzku a, Vlavo u - otoci sa o u stupnov vlavo, Vpravo u - otoci sa o u stupnov vpravo. Korytnacka moze pri kresleni cez jednu ciaru prejst aj viackrat.
Poznamka: Na ladenie svojho programu mozete napriklad v Turbo Pascale pouzit kniznicu Graph3, konkretne jej funkcie GraphMode, Forwd, TurnLeft a TurnRight.
3. Z Pismenkovej ulice
Pismenkova ulica ma velmi zvlastnych obyvatelov. Hlavne vsetkym velmi zalezi na tom (ako to uz byva), co o nom povedia susedia. Napriklad ked si clovek vecer zasvieti, ale vonku nie je este taka tma, susedia si budu o nom na druhy den povravat: "Vsimnite si, on vobec nevie setrit elektrinou!" No musite uznat, ze to nie je velmi prijemne. Ale tazko povedat, kedy si uz mozno bez obav zasvietit. Preto vecer kazdy nenapadne pozoruje, ci uz niekto zo susedov (teda niekto z ludi byvajucich nad, pod alebo vedla) nezasvietil. Ak ano, potom uz moze aj on. Nastastie vzdy sa najde niekto, kto to uz psychicky nevydrzi a napriek vedomiu, ze ho na druhy den bude ohovarat cele susedstvo, zasvieti. Potom to uz postupuje jedna radost, az nakoniec svietia vsetky okna bytov, kde je niekto doma (mozete predpokladat, ze ak sa na zaciatku rozsvieti jedine okno, na konci budu vsetky okna, kde je niekto doma rozsvietene).
Uloha: Na vstupe je dany pocet poschodi a pocet okien na jednom poschodi domu na Pismenkovej ulici. Dalej je dany pocet okien, kde nikto nie je doma a zoznam tychto okien. Kazde okno je dane dvojicou A,B, kde A je poschodie a B cislo okna na poschodi zlava. Dalej je dane okno, kde to nevydrzali a zasvietili. Odsimulujte na obrazovke jeden zo sposobov, ako sa mozu rozsvecovat ostatne okna.
4. Zlo volejbalovych majstrovstiev
V Nalomenej Trieske sa kazdorocne pri prilezitosti oslav zalozenia obce konaju Majstrovstva Nalomenej Triesky vo volejbale. Je to velka udalost a kazdy obyvatel povazuje za cest zucastnit sa na majstrovstvach ako hrac. Kazdy rok sa preto vybrali najlepsi hraci, rozdelili sa do druzstiev a hry sa mohli zacat. Az pred par rokmi sa zacalo ozyvat coraz viac protestnych hlasov, ze vybrati hraci vobec nie su najlepsi a preco by sa aj ostatni nemohli hier zucastnit a... A vobec!
Nakoniec starosta Nalomenej Triesky prisiel na salamunske riesenie. V den majstrovstiev prikazal vsetkym zaujemcom o hru rovnomerne sa rozmiestnit na luke. Potom sa nahodne urcila poloha ihriska. Vsetci, ktori sa nachadzali na ihrisku, sa mohli majstrovtsiev zucastnit ako hraci, ostatni ako divaci. Tento sposob sa hned vsetkym viac pacil. A tak sa odvtedy hraci urcuju takto a v Nalomenej Trieske znova panuje zhoda a pokojna atmosfera.
Uloha: Na vstupe su dane suradnice rohov ihriska (ihrisko je obdlznik), siet je rovnobezna s kratsou stranou ihriska a deli ho na dva rovnake obdlzniky. Dalej je dany pocet ludi, ktori sa rozhodli zucastnit sa hry, a suradnice kazdeho z nich. Zistite, ktori budu hracmi prveho druzstva, ktori druheho a ktori z nich budu divaci.
Poznamka: Clovek nachadzajuci sa presne na okraji ihriska, sa tiez stava hracom jedneho z druzstiev. Ten, kto sa nachadza na urovni siete, je do druzstva prideleny nahodne.
Priklad:
Vstup:
Ihrisko: (0,2), (1,4), (5,2), (4,0)
Pocet ludi: 4
Suradnice ludi: (1.2,3), (4,4), (2,3), (3,2)
Vystup: Hraci prveho druzstva: (1.2,3), (2,3)
Hraci druheho druzstva: (3,2)
Divaci: (4,4)
5. Zachrante nas!
KRAL SA ZBLAZNIL stop SETRIT CHCE stop PENIAZE ZRUSIL stop DAL TLACIT NOVE stop IBA DVA DRUHY stop CHCEME MU UKAZAT ZE JE TO HLUPOST stop ZE SA NEDA VSETKO ZAPLATIT stop ZAKAZAL VYDAVAT PENIAZE SPAT stop POMOZTE NAM stop RYCHLO stop
Uloha: Napiste program, ktory dostane na vstupe dve prirodzene cisla p a q (hodnoty minci) a vypise NAJVACSIU hodnotu, ktora sa pomocou minci len tychto dvoch hodnot a bez vydavania penazi spat, zaplatit neda. Ak taka hodnota neexistuje, program o tom poda spravu.
Priklad:
Vstup: Vystup: p=3,q=5 7 p=1,q=10 da sa vsetko p=6,q=8 neda sa nekonecne vela hodnot
(C) 1997, Organizers of the CSP
