• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Priklady 1. kola

1. O recidivistoch
2. O hliadkach
3. O leteckej spolocnosti
4. O tvrdohlavom ucitelovi
5. O funkcionalnom programovani I

Mili nasi riesitelia,

vitame Vas v novom rocniku Korespondencneho seminara z programovania - kategoria KSP. 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 20. oktobra 1997.

Kazdy vecer si umyvajte zuby!

KSPaci

---

1. O recidivistoch

Nepokoje v nasich vazniciach narastaju do neunosnych medzi. A to nielen preto, ze su preplnene, ale aj preto, ze recidivistom su vzdy pridelene nove cisla a nie tie ich, na ktore si uz zvykli. Vo vazniciach, kde sa vsetci oslovuju cislami, je tento fakt velmi nevitany.

Vsetko vyriesi novy projekt Alcatras II. Ak pride do tejto vaznice dalsi vazen, bachari zadaju do pocitaca jeho meno a priezvisko a program vypise NOVY, ak tu este predtym vazneny nebol, alebo RECIDIVISTA, ak neprisiel poprvy raz. Program tiez vypise cislo vazna. Novemu vaznovi moze program priradit lubovolne cislo, ktore nema iny vezen, ale recidivistovi musi priradit cislo z jeho predchadzajuceho pobytu. Mozno predpokladat, ze cisla su priradovane iba uvedenym programom.

Uloha: Vytvorte horepopisany program tak, aby fungoval co najrychlejsie a pre co najvacsie mnozstva vaznov. Program bude uvedeny do prevadzky zaroven s otvorenim vaznice, takze vaznica je na zaciatku prazdna. Kedze Alcatras II nikdy nepadne, moze program fungovat v nekonecnej slucke. Mena vaznov su zlozene z velkych pismen abecedy a z medzier.

Priklad:
Vstup a vystup:
? LEX LUTHOR
NOVY 3560
? JAMES BOND
NOVY 007
? LEX LUTHOR
RECIDIVISTA 3560
? LUISE LANE
NOVY 806070
? JAMES BOND
RECIDIVISTA 007

---

2. O hliadkach

Serzant Sergej je velitelom hradnej straze. Je zodpovedny za to, aby pri brane vzdy stala hliadka v pocte K vojakov. Serzant je velmi starostlivy clovek. Aby nikomu zo svojich vojakov neukrivdil tym, ze bude musiet hliadkovat castejsie ako niekto iny, rozhodol sa viest si presnu evidenciu. Zapisovat vzdy mena vsetkych, co boli na strazi je velmi zdlhave a navyse by vsetky tie zapisy zaberali vela miesta. Rozhodol sa teda, ze bude skupinky svojich vojakov kodovat co najuspornejsie - cislami.

Uloha: Napiste serzantovi procedury pre kodovanie a dekodovanie skupin vojakov. Procedura Koduj nech nacita N - pocet serzantovych vojakov a K - pocet vojakov v hliadke (N>K) a K (roznych) cisel vojakov z intervalu 1... N. Jej vystupom bude prirodzene cislo z intervalu 1... (N nad K), jednoznacne kodujuce danu skupinu vojakov. Naopak, procedura Dekoduj nacita cisla N a K a kod (cislo z intervalu 1... (N nad K)), vyprodukovany procedurou Koduj a vypise cisla vojakov v danej hliadke.

---

3. O leteckej spolocnosti

Novozalozena letecka spolocnost Kiribati Air GmbH ma svoj velky ciel: Vytlacit z trhu vsetku konkurenciu. O tom, ze to mysli vskutku vazne, svedci aj to, ze najala mnozstvo programatorov, aby zabezpecila svojim zakaznikom co najlepsie sluzby.

Uloha: Napiste program, ktory zakaznikovi vypocita minimalny cas cesty medzi dvoma mestami. Vzhladom na to, ze prevadzka lietadiel je financne velmi narocna, neexistuje zatial priama linka medzi kazdymi dvoma mestami - obcas sa stane, ze treba aj niekolkokrat prestupovat. Dlzka jedneho letu nepresiahne 20 hodin, lietadla na vsetkych linkach premavaju kazdy den podla presne stanoveneho casoveho harmonogramu. Lietadla spolocnosti Kiribati Air GmbH nikdy nemeskaju, nezastavi ich ziadna burka, hmla, ci porucha.

Vstupom programu je letovy poriadok (obsahuje pocet liniek, pre kazdu linku mesto a cas odletu, mesto a cas priletu), nasledovany niekolkymi otazkami typu "odkial kam''. Vystup obsahuje pre kazdu dvojicu miest minimalny cas (v hodinach a minutach) potrebny na prepravu, alebo informaciu o tom, ze danu cestu nemozno uskutocnit.

Priklad:
Vstup:
3
Bratislava 15:00 Moskva 23:00
Moskva 05:00 BurundiDC 17:33
Moskva 22:00 Tokio 00:00
Bratislava Tokio
BurundiDc Moskva

Vystup:
Bratislava-Tokio: 33h 00m
BurundiDC-Moskva: Smola

Poznamky: Cas je absolutny. Meno mesta je jedno slovo.

---

4. O tvrdohlavom ucitelovi

Ucitel telocviku Sebe Vrazda ma tento rok velmi hlupych ziakov. Kedze uci telocvik vzdy 2 triedy naraz a ma rad poriadok, vyzaduje, aby sa ziaci na zaciatku telocviku postavili do radu podla triedy. Jeho ziakom to ale velmi dlho trva, tak sa rozhodol, ze ich preusporiada sam. A to nie hocijako, ale tak, ze vzdy presunie 2 susednych ziakov naraz (myslel si, ze to tak bude rychlejsie). Teraz si lame hlavu, ako preusporiadat ziakov na najmensi pocet vymen. Pomozte Sebemu, kym sa nenahneva.

Uloha: Napiste program, ktory dostane na vstup 2N (N < 36) znakov, z ktorych je N-1 znakov A, N-1 znakov B a dva susedne znaky m (ako medzera) a ak existuje, vypise lubovolnu najkratsiu postupnost vymen tak, aby na konci boli vsetky pismena A nalavo od pismen B (na umiestneni medzier na konci nezalezi). Vymena priebieha tak, ze zoberieme 2 susedne pismena a presunieme ich do medzery (na ich miesto sa presunie medzera). Pri vymene nie je mozne navzajom vymenit lave a prave presuvane pismeno. Ak takato postupnost neexistuje, program vypise Neexistuje.

Priklad:
Vstup:
N=5
ABBAmmABAB
Vystup:
ABBAmmABAB
ABBABAAmmB
AmmABAABBB
AAAABmmBBB

Iny vstup:
N=2
BmmA
Vystup:
Neexistuje

---

5. O funkcionalnom programovani I

Program vo funkcionalnom programovacom jazyku pozostava z definicii niekolkych funkcii. Kazda funkcia ma jednu alebo viacero vstupnych premennych, pricom tieto vstupne premenne, rovnako ako vysledok funkcie, nadobudaju hodnoty z mnoziny prirodzenych cisel (pre ucely tohoto prikladu budeme povazovat 0 za prirodzene cislo). Tu je ukazka takehoto programu: m(x,y)=0 <- x=0
m(x,y)=m(x-1,y)+y <- x>0

Klauzuly. Definicia kazdej funkcie pozostava z niekolkych riadkov (tzv. klauzul). Kazda klauzula je tvaru:
< funkcia >(< argumenty >)=< vyraz > <- < podmienka >
kde funkcia je meno funkcie, argumenty je zoznam jej vstupnych premennych oddelenych ciarkami a vyraz urcuje hodnotu, ktoru funkcia nadobudne za predpokladu, ze je splnena podmienka podmienka. Ak by mala byt podmienka vzdy splnena, mozno ju celkom vynechat.

Priklad: Pozrime sa, ako sa vyhodnoti funkcia z nasho prikladu pre vstupne premenne x=2 a y=3:

m(2,3) = m(1,3)+3 = (m(0,3)+3)+3 = (0+3)+3 = 6

Najprv (rovnost 1) sa v definicii funkcie nasla klauzula, ktora zodpoveda vstupnym premennym. Kedze x>0, vybrala sa druha klauzula z definicie. m(2,3) sa nahradilo pravou stranou rovnosti v klauzule. Hodnotu vyrazu este stale nevieme priamo urcit, lebo sa v nom vyskytuje volanie funkcie m. Musime teda znovu pouzit definiciu funkcie m (pre hodnoty x=1 a y=3). Opat vyberieme druhu klauzulu (rovnost 2). Vo vyraze este stale vystupuje funkcia m, tentokrat vsak so vstupmi x=0 a y=3, cize pouzijeme prvu klauzulu. Dostaneme tak vyraz, v ktorom sa vyskytuje uz iba znama funkcia +, a ktoreho hodnotu teda vieme spocitat. Ak si program dobre prezriete, zistite, ze tajomna funkcia m pocita sucin svojich dvoch vstupov.

Vylucnost klauzul. Vsetky klauzuly pre jednu funkciu musia splnat tzv. podmienku vylucnosti klauzul. To znamena, ze pre lubovolne vstupne hodnoty musi byt podmienka na pravej strane splnena nanajvys pre jednu klauzulu tejto funkcie (tym zaistime, ze funkcia ma vzdy jednoznacnu hodnotu). Ak nie je splnena podmienka ziadnej klauzuly, funkcia implicitne nadobuda hodnotu 0.

Preddefinovane funkcie. V programe je mozne pouzivat preddefinovane funkcie + a -. Funkcia +(a,b) vrati sucet cisel a,b. Funkcia -(a,b) vrati rozdiel cisel a,b ak a>= b (a teda rozdiel je prirodzene cislo) alebo vrati 0, ak a< b (v tomto pripade by bol rozdiel zaporny a zaporne cisla nemame). Pre zvysenie prehladnosti budeme pisat a+b namiesto +(a,b) a a-b namiesto -(a,b).

Podmienky a vyrazy. Podmienka moze obsahovat logicke spojky "\/" (t.j. "and", konjukcia), znamienka < , >, <=, >=, = a < > a vyrazy. Vyraz v klauzule moze obsahovat zatvorky, konstanty (ako napriklad 0, 1, 63 apod.), vstupne premenne, preddefinovane funkcie a funkcie definovane v programe, vratane rekurzivnych volani.

Poznamka: Ak je v podmienke niektorej klauzuly jednoznacne urcena hodnota niektorej vstupnej premennej, mozno tuto premennu v celej klauzule nahradit touto hodnotou. Napriklad klauzulu m(x,y)=0 <- x=0 mozno zapisat aj takto: m(0,y)=0.

Chvostova rekurzia. Funkcia je napisana chvostovou rekurziou, ak na pravej strane kazdej jej klauzuly sa vyskytuje najviac jedno rekurzivne volanie a to nie v podmienke, toto rekurzivne volanie nie je vstupnou hodnotou ziadnej inej funkcie a vsetky dalsie funkcie, ktore sa v klauzule vyskytuju, su napisane chvostovou rekurziou alebo su preddefinovane.

Vyznam chvostovej rekurzie spociva v tom, ze takuto rekurziu mozno efektivnejsie realizovat (pri prepise do inych programovacich jazykov by bolo mozne zapisat takuto funkciu pomocou cyklu). Nas priklad nie je napisany chvostovou rekurziou, lebo v druhej klauzule je rekurzivne volanie m(x-1,y) vstupnou hodnotou pre funkciu +.

Priklad: Zapiseme teraz funkciu m pomocou chvostovej rekurzie. Pri definicii pouzijeme pomocnu funkciu m_1 s tromi vstupmi, ktora je definovana tiez chvostovou rekurziou. m_1(x,y,z)=z <- x=0
m_1(x,y,z)=m_1(x-1,y,z+y) <- x>0
m(x,y)=m_1(x,y,0)

Uloha: Napiste definicie dvoch doluuvedenych funkcii pomocou chvostovej rekurzie. Mozete pouzivat aj definicie inych funkcii, ale treba si ich naprogramovat (prirodzene, tiez chvostovo rekurzivne). Preddefinovane su len funkcie + a -. Nezabudnite popisat vyznam jednotlivych vstupnych hodnot a pomocnych funkcii a odovodnit spravnost vasho programu.

• a) f(0) = 0
  f(1) = 1
  f(n+2) = f(n) + f(n+1), n>= 0
  
• b) g(n) = horna cela cast odmocniny z n.

Priklad:

  x   0   1   2   3   4   5   6    7   ...
f(x)  0   1   1   2   3   5   8   13   ...
g(x)  0   1   2   2   2   3   3    3   ...

Poznamka: Snazte sa, aby Vas program pracoval co najrychlejsie (vzhladom k poctu volani funkcii), ale radsej program pomaly a dobry ako program zly.

---

(C) 1997, Organizers of the CSP

---