- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 2. kola
Mili nasi riesitelia,
je uz peknou tradiciou, ze pod vianocnym stromcekom sa okrem auticiek, elektrickych vlacikov a babik zaskvu aj zadania 2. kola KSPecka. Ani tohto roku sme vas nesklamali, svoje oblubene zadania najdete na nasledujucich strankach! Aby sa pod stromcekom len tak bezducho nevalali, termin sme stanovili na 5. januara 1997.
Takze, akurat nejake pekne prianie do noveho roku
Co mozes urobit dnes, neodkladaj na zajtra.
KSPaci
- O kolaci II.
- O univerzitnom knihovnikovi II.
- O vrabcovi Cin-cinovi II.
- O kiribatskych naleziskach II.
- O Stevovej sieti II.
1. O kolaci II.
Na obdlznikovom plechu upiekli (mimochodom nie velmi dobry) kolac velmi velkych rozmerov. Kolac sa navyse na krajoch pripalil a tie drzali na plechu ako prilepene kanagonom.
Hostia sa uz zisli, nikto nevie co im ponuknut, tak sa rozhodli, ze predsa len nieco z toho plechu vydoluju. Zobrali noz a zacali do kolaca rezat zvisle a vodorovne usecky, ktore sa nedotykali pripalenych okrajov.
Potom plech preklopili, vysypali kusky rychlo na tanier a odniesli ich hostom. Zaujimavou otazkou vsak zostava, kolko dier zostalo v povodnom kolaci.
Uloha: Danych je N zaciatocnych a koncovych bodov jednotlivych useciek vyrezanych do kolaca. Napiste program, ktory zisti, kolko dier zostalo v kolaci po vyklopeni plechu.
Priklad:
2. O univerzitnom knihovnikovi II.
"Oook!" zacudoval sa knihovnik, ked zistil, ze dnes su na polici zase ine knihy. Vcera polica obsahovala niekolko prvych a druhych dielov Lindenmayerovho zbornika magickych formul. Aj dnes tam boli prve a druhe diely toho isteho zbornika, ale urcite sa lisil ich pocet a rozmiestnenie. Ked knihovnik niekolko dni knihy pozoroval, zistil, ze ich zmeny nie su nahodne. Kazdu noc z kazdeho 1. dielu vznikne skupina knih u a z kazdeho druheho dielu vznikne skupina knih v, pricom u a v su kazdu noc tie iste. Tak sa rozhodol dat Mrakoplasovi ulohu. Napisal mu na papier nejake poradie prvych a druhych dielov a prikazal mu zistit, ci niektory den bude na polici taka ista skupina prvych a druhych dielov ako je na papieri (nalavo aj napravo od tejto skupiny mozu byt na polici este dalsie knihy).
Uloha: Pomozte Mrakoplasovi a napiste program, ktory zisti odpoved na knihovnikovu ulohu. Program nacita postupnosti u, v, w, x pozostavajce z cisel 1 a 2, kde u je skupina knih, na ktore sa kazdu noc zmeni kniha 1, v je skupina knih, na ktore sa zmeni kniha 2, w je dnesny stav police a x je knihovnikov zoznam (u a v mozu byt aj prazdne postupnosti).
Priklad:
Nech u=12, v=212, w=21. Teda kazdu noc sa kazda
1 zmeni na 12 a kazda 2 sa zmeni na 212. Na
druhy den budu na polici knihy 21212 a na treti den 2121221212212.
V pripade, ze x=1221, odpoved na knihovnikovu otazku bude ano,
lebo takato skupina sa nachadza v postupnosti knih tretieho dna. V pripade,
ze x=11, odpoved bude nie, lebo takato skupina nikdy nemoze
vzniknut.
3. O vrabcovi Cin-cinovi II.
Vrabec Cin-cin zase priletel neskoro. Bolo to uz piate pomaturitne stretnutie a doteraz sa mu este nikdy nepodarilo priletiet vcas. Aby nenarobil zmatok a nepokazil veselu zabavu, chcel si uz vopred vyhliadnut miestecko, na ktore sa posadi.
Vzdy sedavali na prvom drote hned za dedinou, na useku od stlpu EV 274 po stlp EV 277. Cin-cin nerad sedaval na kraji, pretoze tam sa mohol rozpravat len s jednym zo svojich susediacich (nakolko vrabec na kraji ich viac nema). Ale na druhej strane, Cin-cin ma rad okolo seba miesto. Preto by si teraz najradsej sadol medzi tych dvoch susednych vrabcov, ktori su od seba najviac vzdialeni. Z tolkej dialky vsak nedovidi na starych kamaratov. Nastastie blizko sedi straka Rapotajka, ktora si iste tuto nevsednu udalost nenechala ujst a ma o vsetkom prehlad. A naozaj. Rapotajka Cin-cinovi vyrapotala, kedy ktory vrabec prisiel a kam sa usadil.
Uloha: Napiste Cin-cinovi program, ktory nacita dlzky drotu A, B od stlpov EV 274 a EV 277 do dediny, dalej nacita N doteraz usadenych vrabcov a ich vzdialenost po drote od dediny. Program vypise dvoch susednych vrabcov, ktori su spomedzi vsetkych susednych vrabcov najviac od seba vzdialeni.
Poznamka: Riesenia linearne od poctu vrabcov N su velmi vitane.
Priklad:
Vstup:
A=5, B=16
N=5
Polohy vrabcov: 9,13,7,15,10
Vystup:
Najvzdialenejsi su si vrabci sediaci na polohach 10 a 13.
4. O kiribatskych naleziskach II.
Na Kiribatskych ostrovoch nedavno objavili pod zemou velke zasoby rumu II. Po predchadzajucich skusenostiach inzinieri postavili jednu velku vrtnu vezi, problemom je vsak preprava rumu II. z tejto veze.
Po niekolkych duskoch inzinieri navrhli vybudovat velku rumarensku siet skladajucu sa z rumovodov a z regulacnych stanic (na kazdej rure je umiestnena tzv. cuchacka, cez ktoru moze povereny pracovnik udrzbovej skupiny ocuchavat, ci rum nahodou nevyteka mimo rumovod). Kazdou rurou moze pretiect hektoliter rumu za minutu. Regulacne stanice su miesta, v ktorych sa stretava jedna alebo viacero rur, ktore su v tomto mieste prepojene. Plati zasada, ze pritok do regulacnej stanice a vytok z nej su v rovnovahe (vplyv zamestnancov regulacnej stanice na porusenie tejto rovnovahy po vzore priatelov fyzikov zanedbame). Cela siet je v regulacnej stanici s priamo napojena na vrtnu vezu a rum je odcerpavany zo siete v mestskej regulacnej stanici t.
Rano inzinieri nad svojim navrhom triezvo pouvazovali a zistili, ze stavba by to bola sice velkolepa, ale rumu by sa cez nu vela do mesta neprepravilo.
Uloha: Dany je pocet regulacnych stanic N, pocet rumovodov M a dalej M dvojic cisel reprezentujucich jednotlive rumovody (od ktorej regulacnej stanice ku ktorej vedu), pricom stanica s ma cislo 1 a stanica t ma cislo N. Napiste program, ktory vypocita, kolko rumu za minutu je takto navrhnuty rumovod schopny prepravit.
Poznamka: Predpokladajte, ze vytazit mozno tolko rumu, kolko z s odtecie a ze v t odcerpavaju bezo zbytku vsetok rum, ktory tam pritecie.
Priklad:
Vstup:
N=4, M=5
Rumovody: (1,2), (2,3), (1,3), (3,4), (1,4)
Vystup:
Cez rumarensku siet pretecu najviac 2 hektolitre rumu za minutu.
5. O Stevovej sieti II.
Oprava zadania O Stevovej sieti: Nase historicko-vyskumne oddelenie zistilo, ze Stevo nemohol jest kalerab, kedze kaleraby vobec nema rad. Spravna zelenina na tomto mieste bola mrkva.
Stevo dojedol svoju mrkvu, poobhliadal sa po okoli, coze to robia jeho kamarati a zhrozil sa. V pocitacovej sieti panoval uplny chaos! Stevo zacal liezt po stromoch, rozpajat, prepajat a zapajat nove kable a po niekolkych minutach pospajal pocitace pekne do kruhu. A spokojne na svoje dielo pozeral.
I Stevo povedal: ak chcete riesit akukolvek ulohu, musite zvolit sefa! A studenti Matematicko-fyzikalnej fakulty sa zamysleli nad Stevovymi slovami a videli, ze to co vravi, je dobre.
Uloha: Kazdy pocitac je spojeny s dvoma susednymi pocitacmi v kruhu, s kazdym osobitnou linkou. Linky maju cisla 1 (lavy sused) a 2 (pravy sused). Kazdy pocitac v sieti ma jednoznacne priradene meno (retazec max. 10 pismen, ktory neobsahuje medzery - napriklad FERDO). Ak su pocitace A a B spojene linkou, moze napriklad pocitac A poslat spravu pocitacu B, sprava sa zaradi do mailboxu pocitaca B.
Napiste program, ktory (pokial rozmyslaju o Stevovych slovach) spustia vsetci Stevovi kamarati na svojich laptopoch, pricom po jeho skonceni bude kazdy pocitac poznat meno sefa (kedze sef moze byt len jeden, kazdy pocitac musi zistit to iste meno, je vsak uplne jedno, ktory z pocitacov bude sefom). Program bezi na kazdom pocitaci nezavisle.
Pre komunikaciu medzi pocitacmi mate k dispozicii tieto procedury (pre jazyk C, pripadne iny jazyk zadefinujte procedury s podobnou strukturou; smes je to iste co string, iba s neobmedzenou dlzkou):
- Send(sprava:smes; linka:integer) - pocitac posle spravu sprava po linke linka.
- Receive(var sprava:smes; var linka:integer) - vyberie z mailboxu jednu spravu a vrati v premennej sprava jej obsah a v premennej linka udaj o tom, z ktorej linky sprava prisla. Ak ziadna sprava v mailboxe nie je, Receive caka az kym tam nejaka nebude.
- MyName(var s:string[10]) - do premennej s ulozi meno pocitaca.
Poznamka: Snazte sa, aby pocitace skoncili skoro, aby studenti prilis dlho nerozmyslali nad Stevovymi slovami, mohlo by to mat nedozierne nasledky. Linky su pomale a preto sa snazte, aby ste toho neprenasali zbytocne vela.
(C) 1996, Organizers of the CSP
