- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 1. kola
Mili nasi riesitelia,
vitame Vas pri rieseni noveho rocnika KSP. Dufame, ze aj tento rok sa Vam nase ulohy budu pacit a ze sa do sutaze zapojite v hojnom pocte. Riesenia prveho kola nam posielajte do 19. oktobra 1998. Predtym, ako nam poslete svoje riesenia prveho kola, nezabudnite si pozorne precitat propozicie. Spolu s rieseniami nam poslite vyplneny evidencny listok a dvoj a trojkorunove znamky v celkovej hodnote 10.- Sk.
KSPaci
- O Kubomire
- O pazravej Livii
- O predvolebnych mitingoch
- O vyskumnicke Janke
- O profesorovi Indigovi a vile Amalke I
1. O Kubomire
Kubomir je nanajvys jednotvarne miesto. Pozostava z n stvorcovych policok usporiadanych do radu vedla seba. V Kubomire zije jediny druh zivocicha - kubar, a jedna nadzmyslova neuchopitelna bytost bez tvaru, farby, chuti a zapachu - Kuboh.
Kubar ma tvar kocky - vznikne, kedy a kde si Kuboh zmysli. Kubar potom proste JE, EXISTUJE, ale inak nic - ani sa nepohne. Potom si zrazu Kuboh zmysli, ze kubar zanikne, a kubar naozaj zanikne. Kuboh si zavse zmysli niekolko novych kubarov vedla seba, napriklad od policka a az po policko b. Hned nato pribudne po jednom kubarovi na polickach a,a+1,a+2,...,b-1,b. Takisto si moze Kuboh zmysliet, ze zanikne po jednom kubarovi na polickach c az d. Kuboh je neomylny, teda nieco take si zmysli iba vtedy, ked na tychto poziciach je po aspon jednom kubarovi. A takto stlpce kubarov na jednotlivych polickach Kubomiru stupaju a klesaju.
Z casu na cas sa Kuboh filozoficky zamysli: "A kolkoze to mame kubarov na r-tom policku?" Alebo: "A na kolkychze polickach mame aspon jedneho kubara?" Z dlhej chvile sa naucil programovat a teraz travi dlhe chvile dumanim nad tym, ako by to naprogramoval. Ukazte, ze ste aspon taki dobri ako Kuboh.
Uloha: Je dany pocet policok Kubomiru n. Na zaciatku je Kubomir prazdny. Na vstup prichadzaju spravy, ktore vasmu programu oznamuju vsetky zmeny v Kubomire, alebo pozaduju nejake hodnoty o aktualnom stave. Ulohou vasho programu je pomocou vhodnej reprezentacie stavu Kubomiru spravne a rychlo reagovat na vsetky spravy a poskytovat pozadovane udaje. Kazda sprava je jedneho z nasledujucich typov:
- VZNIK a b
- na polickach a az b vzniklo po jednom kubarovi (1<=a<=b<=n).
- ZANIK c d
- na polickach c az d zaniklo po jednom kubarovi (1<= c<= d<= n; mozete predpokladat, ze na polickach c,...,d predtym bolo aspon po jednom kubarovi).
- VYSKA r
- vypiste, kolko kubarov je na r-tom policku tajnicky (1<= r<= n).
- ASPON JEDEN
- vypiste, na kolkych polickach sa nachadza aspon jeden kubar.
Priklad:
n=6
> VZNIK 2 6
> VZNIK 4 4
> VYSKA 5
1
> ZANIK 2 4
> ASPON JEDEN
3
Ako sa menil Kubomir:
2. O pazravej Livii
"Meeeeeeeee, meeeeeeeee," zacula teta Anastazia zo svojho domceka. Koza Livia sa znovu priblizila az k domceku na koniec zahrady. A tam ma teta Anastazia posadenych najviac kvetov. Dnes ju uz aspon osemkrat vyhnala past sa na iny koniec, kde tych kvetov nie je az tolko, ale marnost nad marnost! Tak sa nakoniec teta Anastazia s tazkym srdcom rozhodla Liviu priviazat. Zacala v zahrade hladat co najvacsiu plochu taku, aby tam neboli ziadne kvetiny a aby Livia mala dost velky priestor na pasenie sa.
Uloha: Teta chce priviazat kozu Liviu spagatom o kolik. Potrebuje najst take miesto na zapichnutie kolika, aby sa Livia mohla past na co najvacsej ploche, ale pritom musi zvolit taku dlzku spagatu, aby Livia nemala v dosahu ziadnu kvetinu a nemohla vyjst za hranicu zahradky. Zahrada ma tvar obdlznika A x B.
Napiste program, ktory nacita rozmery zahradky A x B, pocet kvetov N a suradnice jednotlivych kvetin (x1,y1) az (xN,yN) a najde stred a polomer kruznice s najvacsou plochou, ktora lezi cela v zahradke a neobsahuje ziadnu kvetinu.
Priklad:
Vstup:
Rozmery zahradky: A = 3.0, B = 2.0
N=5
Kvety:
(0.5, 0.5), (0.5, 1.5),
(1.5, 0.5), (1.5, 1.5),
(2.5, 0.5)
Vystup:
Stred: (2.225, 1.225)
Polomer: 0.775
3. O predvolebnych mitingoch
Kral Burundi sa dival na klesajuci graf svojich preferencii. Nie ze by to bol dovod na znepokojenie, ale bolo mu z toho smutno. I dal si zavolat hlavneho radcu a spytal sa ho, co s tym. Radca poradil: "Ludia maju radi zmenu a vase Velicenstvo sedi na trone uz desat rokov. Ponuknite im ju, usporiadajte volby!" Kral sa zhrozil, ked mu vsak jeho poradca vysvetlil, ze bude len jeden kandidat, nadsene suhlasil.
Onedlho si uz kral prezeral vypracovany harmonogram predvolebnych mitingov. Na zozname vzdy bolo mesto a den, kedy sa tam bude konat miting. Ked sa kral prizrel lepsie, s hrozou zistil, ze mitingov je prilis vela a ze sa nestihne vsetkych mitingov zucastnit. Burundi je totiz velka krajina so zlymi cestami, preprava z jedneho mesta do ineho moze trvat aj niekolko dni. Kral nevahal a slubil okamzite 50 percent akcii Zapadoburundijskych Zeleziarni tomu, kto mu najde taku trasu predvolebneho vyjazdu, aby stihol co najviac mitingov.
Uloha: Burundi ma N miest ocislovanych 1 az N. Mate k dispozicii zoznam burundijskych ciest (vsetky su obojsmerne), pre kazdu cestu viete, ako dlho trva jej prejdenie autom. Dalej pre kazdy miting viete, v ktorom meste a ktory den sa kona. Kral je v den 0 v hlavnom meste (mesto c. 1). Kral sa na mitingoch zdrzi iba zanedbatelny cas, jeho predvolebna cesta nemusi koncit v hlavnom meste. Napiste program, ktory nacita zoznam burundijskych ciest a zoznam mitingov a zisti, kolko najviac mitingov moze kral stihnut.
Priklad:
Vstup:
4 mesta
cesty:
z 1 do 2 za 4 dni
z 1 do 3 za 3 dni
z 2 do 3 za 4 dni
z 2 do 4 za 5 dni
z 3 do 4 za 2 dni
mitingy:
mesto 1 den 3
mesto 2 den 4
mesto 3 den 9
mesto 1 den 12
mesto 4 den 17
Vystup:
Daju sa stihnut najviac 4 mitingy.
4. O vyskumnicke Janke
Janka je vyskumnicka a pracuje v laboratoriu na vyskum inteligencie zivocisnych druhov. Inak je to mala biela myska, ktora ma rada syr. Po niekolkych tyzdnoch trpezlivej prace sa jej podarilo vycvicit si svojho cloveka. Vzdy, ked Janka vybehne po rebriku, dostane kusok chutneho syra.
Teraz vsak Janka nie je hladna. Okolo seba mala porozhadzovanych niekolko kociek s pismenami. Vacsinu upratala kdesi do kuta, ale zopar ich tu stale ostalo. Len tak na skusku ich usporiadala tak, aby pismena na nich tvorili palindrom, t.j. slovo, ktore je rovnake, ci ho citate spredu alebo odzadu. Ake bolo jej prekvapenie, ked o chvilu prisiel clovek s kusom ementalu a hrbou dalsich kociek. Poukladal ich do radu a nenapadne sa vzdialil. Janke bolo hned jasne, co od nej clovek chce. Medzi poukladane kocky ma povsuvat niekolko dalsich tak, aby vznikol palindrom. Ihned zacala premyslat, kolko najmenej kociek bude treba do radu vsunut (kocky su tazke a Janka sa nechce prilis namahat).
Uloha: Napiste program, ktory nacita vstupne slovo w = a[1]a[2]...a[n] a zisti, kolko najmenej pismen musime pridat, aby z neho vznikol palindrom. Nove pismena mozeme vsuvat medzi lubovolnu dvojicu susednych pismen, na zaciatok a na koniec. Jeden takto vzniknuty palindrom aj vypiste.
Priklad:
Vstup:
abab
obyamamalybk
Vystup:
babab (pridanych pismen: 1)
kobylamamalybok (pridanych pismen: 3)
5. O profesorovi Indigovi a vile Amalke I
Iste ste si vsimli, ze dobry koniec mnohych rozpravok maju na svedomi rozne dobre vily a im podobne zivly, ktore ked je najhorsie, daju hlavnemu hrdinovi dobru radu. Vsimol si to aj profesor Indigo a hned vymyslel, ako by sa dala tato ich dobra vlastnost vyuzit. Indigo si uvedomil, ze aj ked pocitace vedia riesit mnoho uloh, niekedy ani ony nevedia, kam z konopi. Obcas by sa aj pocitacu hodila nejaka dobra rada. Profesor sa rozhodol skonstruovat prefikany pocitac ( PP ), ktory bude tazit zo spoluprace s dobrou vilou. Dohodol sa s vilou Amalkou, ze bude pomahat prefikanemu pocitacu s vypoctami. Tak vznikol pocitac Amalka inside.
Prefikany pocitac vie riesit ulohy, na ktore je odpoved ano/nie. Profesor prenho spravil aj kompilator Pascalu (resp. C/C++), ktory zatial nepodporuje ziadne prikazy na pracu so vstupno-vystupnymi zariadeniami (ako obrazovka, klavesnica alebo disk). Na odovzdavanie vstupnych udajov programu sa pouzivaju parametre odovzdavane pomocou rezervovaneho slova program. Aby bolo mozne ako parametre odovzdavat aj zlozene typy, povolil deklaracie typov a konstant pred slovom program. Napriklad
const MAX = 10; type bod = record x,y : integer; end; program MojPrg(B : bod; p : array[1..MAX] of byte);
je hlavicka programu, ktory na vstupe dostane jeden udaj typu bod a pole 10 bajtov. Specialne prikazy fail a accept sluzia na ukoncenie programu. Prikaz accept znamena, ze program da odpoved ano. Prikaz fail znamena cosi ako ``nepodarilo sa mi dat odpoved ano'' (presnejsi popis dalej).
Poslednou novou konstrukciou je prikaz choose, ktory ma rovnaku strukturu ako prikaz case, az na to, ze neobsahuje ziadny vyraz, podla ktoreho sa program vetvi. Napriklad
choose 1 : Prikaz1; 2 : begin Prikaz2; Prikaz3; end; end;
Vzdy ked Amalka inside narazi pri vykonavani programu na prikaz choose, vila Amalka rozhodne, ktora vetva sa vykona.
V jazyku C/C++ sa vstupne udaje odovzdavaju ako parametre funkcie main. Prikazy fail a accept funguju podobne ako return, az na to, ze nemaju ziadne parametre a ukoncuju program. Konstrukcia choose je analogiou konstrukcie switch bez riadiaceho vyrazu - Amalka rozhodne, na ktore navestie case treba skocit (pre ine programovacie jazyky si navrhnite obdobne konstrukcie sami).
Amalka riadi beh programu tak, aby vzdy, ked to je mozne, bola odpoved ano. To znamena, ze vzdy, ked pre dany vstup existuje taka postupnost vetveni choose, ktora dovedie program k prikazu accept, Amalka inside da odpoved ano. Ak takato postupnost neexistuje, Amalka inside da odpoved nie (Amalka ako spravna vila vie predpovedat, ze ziadna postupnost vetveni nevedie k prikazu accept a zastavi vypocet). Amalka inside da teda odpoved nie, ak kazda z postupnosti vetveni choose vedie bud k prikazu fail, k inemu sposobu skoncenia programu, alebo vypocet pri tejto postupnosti bezi donekonecna.
Profesor Indigo napisal prvy program pre prefikany pocitac. Tu je:
const MAX = 100;
type pole = array[0..MAX-1,0..MAX-1] of integer;
program PrvyProgram(N : integer; p : pole);
var x,y : integer;
begin
x:=0; y:=0;
repeat
choose
vlavo: x:=x-1;
vpravo: x:=x+1;
hore: y:=y-1;
dole: y:=y+1;
end;
if (x<0) or(x>=N) or (y<0) or (y>=N) then fail;
if p[x,y]<>0 then fail;
if (x=N-1) and (y=N-1) then accept;
until false;
end.
Profesor si vsak nie je celkom isty, ci vsetko pracuje tak, ako ma. Pre kontrolu by potreboval program, ktory robi presne to iste, ale nevyuziva schopnosti vily Amalky.
Uloha: Napiste program, ktory robi presne to iste ako profesorov prvy program (t.j. na rovnake vstupy davaju oba programy rovnake odpovede), ale nepouziva konstrukciu choose a vzdy skonci prikazom accept alebo fail (vas program teda nepotrebuje vilu Amalku).
1998, Organizers of the CSP
