KSP
- Home
- Novinky
- Pravidlá
- FAQ
- Kuchárka
- Liaheň
Séria
Akcie
Ostatné
Iné semináre
- Trojsten
- KMS
- FKS
- Iné súťaže

Korešpondenčný seminár z programovania

Priklady 2. kola

Mili nasi riesitelia,

blizia sa vianoce a tak aj my chceme prispiet k vianocnej nadielke a to sposobom nam vlastnym - je tu druha seria KSPcka. Vase riesenia nam posielajte do 7. januara 1998. Uz sa na ne tesime. A nezabudnite na znamky! A este Vam chceme pripomenut:

Kazde rano si umyvajte zuby!
KSPaci

O prevrate
O komercionalizacii zlatokopectva
O autickach
O vrtoch v Legolande
O funkcionalnom programovani II

1. O prevrate

V istej nemenovanej krajine za vela horami a aspon tolkymi dolami sa odohral statny prevrat. Stary zly nacelnik Bubutu Sese Kosa bol zvrhnuty a na jeho miesto nastupil mlady Tekila. Ako to po kazdom spravnom prevrate chodi, novy nacelnik nasluboval zrusit vsetky stare (a teda zle) zakony a nahradit ich novymi. I vyhlasoval Tekila nove zakony, rusil stare, az ich vsetky zrusil. Ale zrusil naozaj vsetky pozostatky po starom zlom Bubutuovi? Tekila schytil zbierku zakonov a zacal kontrolovat vsetky zakony, ci pod kazdym je jeho znak. Zbierka zakonov je vsak velmi rozsiahla. Este ze nedavno vysla na CD.

Uloha: Na vstupe je jedna stranka zo zbierky nascanovana vo vysokom rozliseni - obdlznik m x n nul a jednotiek. Takisto je dany Tekilov znak - obdlznik a x b, a <= m; b <= n. Vasou ulohou je napisat program, ktory zisti, ci sa znak nachadza na stranke, t.j. ci sa da znak posunut tak, aby sa presne zhodoval s nejakou oblastou stranky.

Priklad:
Vstup:
m = 5; n = 4; a= 3; b = 3
Znak:

111
010
010

Stranka zo zbierky:

Vystup:
Ano, na stranke je znak. (Na suradniciach 3,1 ma lavy horny roh).

2. O komercionalizacii zlatokopectva

Santo s Bantom sa rozhodli vyuzit roky stravene kopanim zlata prekvapujucim sposobom. Na stare kolena sa rozhodli stat sa sprievodcami po baniach, vykopanych mnohymi zlatokopmi na Vysnej Klondike. Taka bana sa sklada zo sieni, kde sa kedysi kopalo zlato, pospajanych chodbami. Zlatokopi su lenivi chodit do kopca, preto vsetky siene a chodby su v rovnakej vyske. Ziadne dve chodby sa nekrizuju (lebo by dochadzalo k zrazkam vozikov nalozenych zlatom).

Niekolko sieni (takzvane vonkajsie siene) je pospajanych chodbami do vonkajsieho okruhu. Kazda vonkajsia sien je spojena s prave dvoma inymi vonkajsimi sienami chodbou. Vsetky ostatne siene (takzvane vnutorne siene) su vnutri vonkajsieho okruhu. Do bane sa vchadza cez jedinu sien na vonkajsom okruhu. Z kazdej siene vedu prave tri chodby do troch roznych inych sieni (t.j. z kazdej vonkajsej chodby vedie prave jedna chodba do vnutornej siene). Medzi kazdymi dvoma sienami v bani sa da prejst prave jednym sposobom tak, ze nepouzijeme ziadnu chodbu z vonkajsieho okruhu a kazdou sienou prejdeme najviac raz.

Santo s Bantom by chceli pre navstevnikov pripravit okruznu cestu, ktorou by navstevnici presli cez kazdu sien prave raz. Kedze jedna trasa sa rychlo okuka, chceli by ich mat pripravenych niekolko. Na to by radi vedeli, kolko takych okruznych ciest vlastne existuje. Teraz smutne sedia nad mapou bane a snazia sa ich spocitat.

Uloha: Napiste program, ktory nacita n - pocet sieni v bani, k - pocet vonkajsich sieni (3<= k<n <= 1000) a zoznam 3n/2 chodieb medzi sienami a zisti pocet okruznych ciest po bani. Pre jednoduchost predpokladajte, ze siene su cislovane 1... n, siene 1 az k su vonkajsie a sien cislo jedna je vstupna miestnost. Kazda okruzna cesta zacina aj konci v sieni cislo 1. Dve trasy, ktore sa lisia len smerom prehliadky, povazujeme za rozne.

Priklad:
Pre banu na planiku existuje 6 okruznych tras:
1, 5, 4, 6, 8, 7, 2, 3 (a naspat do 1),
1, 8, 6, 5, 4, 2, 7, 3,
1, 5, 6, 4, 2, 3, 7, 8
plus kazda este v opacnom smere.

3. O autickach

Ako vzdy na prednaske, aj dnes Brutus a Frutus nemali co robit. Kedze nemali ziaden dobry casopis, ani knihu, a piskvorky sa im uz hrat nechcelo, pustili sa do novej hry. Auticka sa hraju na stvorcekovom papieri, na ktorom je vyznacena pretekarska draha. Kazdy hrac ma na zaciatku na startovacom bode svoje auticko. Cielom je dopravit toto auticko do cieloveho bodu na co najmenej tahov. V jednom tahu sa moze auticko pohnut o svoj vektor rychlosti, ktory moze hrac pred zaciatkom tahu zmenit o -1, 0, alebo 1 v oboch smeroch (x aj y). Auticko nevie prechadzat stenou, t.j. vektor rychlosti nesmie krizovat miesto mimo drahy. Na zaciatku auticko stoji, v cieli moze mat akukolvek rychlost. Po tom, co Frutus tretikrat za sebou vyhral, rozhodol sa Brutus poziadat vas o pomoc (aby nemusel Frutovi vybit dalsi zub).

Uloha: Napiste program, ktory pre danu trat vypise minimalny pocet tahov, za ktore sa da prejst zo startu do ciela. Trat je zadavana nasledovne: M, N - velkost pola, N riadkov po M znakoch samotna trat ('O' - trat, 'X' - mimo trate), a nakoniec suradnice startu a ciela.

Priklad:
Vstup: M=14, N=14

XXXXXXXXXXXXXX
XOOOOOXXXXXXXX
XOOOOOOXXXXXXX
XOOOOOOOOXXXXX
XOOOXOOOOOOXXX
XOOOXXOOOOOOOO
XOOOOXXOOOOOOO
XXOOOXXXXXXXXX
XXOOOXXXXXXXXX
XXOOOXXXXXXXXX
XXOOOXXXXXXXXX
XXOOOXXXXXXXXX
XXOOOXXXXXXXXX
XXXXXXXXXXXXXX

Start: (3,13) Ciel: (14,6)
Vystup:
Trat sa da prejst na 9 tahov.

4. O vrtoch v Legolande

Na Legolandskej nahornej plosine (alebo skor pod nou) objavili ropu. Majetkuchtivi Lewingovci spravili hned niekolko vrtov. Hned ako zistili, ze na vycerpanie celeho ropneho pola im viac netreba, rozhodli sa, ze si pozemok ohradia. Legolandska nahorna plosina je cela rozdelena na rovnako velke stvorcove policka. Kazde policko ma vyznacny bod - jeho stred. V Legolande cenu pozemku urcuje pocet vyznacnych bodov vnutri pozemku. Lewingovci by boli radi, keby platili co najmenej - len za policka s vrtmi. Stlpy, medzi ktore sa natiahne plot, samozrejme stoja vo vyznacnych bodoch nejakych inych policok.

Uloha: Napiste program, ktory nacita cislo n a suradnice n mrezovych bodov a zisti, ci existuje taky mnohouholnik s vrcholmi v mrezovych bodoch, ktory obsahuje vo vnutri vsetky mrezove body zo zadanej mnoziny a ziadne ine mrezove body. Ak existuje, vypiste zoznam vrcholov lubovolneho vyhovujuceho - za radom po obvode, kazdy zadany svojimi suradnicami; obvod nesmie prechadzat dvakrat tym istym bodom. Ak neexistuje, vypiste o tom spravu.

Poznamka: Mrezove body su body s celociselnymi suradnicami.

Priklad:
Vstup:
n=6
Mrezove body:
(1,2),(1,3),(2,4),(2,1),(3,2),(3,3)

Vystup:
(1,0),(4,2),(3,5),(0,3),(1,1),(2,3),(3,4)

5. O funkcionalnom programovani II

V priklade budeme pracovat s funkcionalnym jazykom opisanym v zadaniach prveho kola. Tento jazyk pouzival iba prirodzene cisla. Kedze neoddelitelnu sucast kazdeho programovacieho jazyka tvoria datove struktury, obohatime ho este o moznost kodovania datovych struktur do prirodzenych cisel.

Preddefinovane funkcie. Okrem funkcii + a - jazyk obsahuje aj dalsiu preddefinovanu funkciu p: N x N -> N s nasledujucimi vlastnostami:

p(x,y) = p(v,w) -> x=v a sucasne y=w, pre vsetky x,y,v,w prirodzene,
0<p(x,y) a sucasne x < p(x,y) a sucasne y < p(x,y), pre kazde x,y prirodzene,
ak x>0, potom existuju prirodzene cisla v,w take, ze x=p(v,w), pre kazde x prirodzene.

Pomocou funkcie p je teda mozne kazdu dvojicu prirodzenych cisel jednoznacne zakodovat do jedneho prirodzeneho cisla a naopak pre kazde prirodzene cislo x>0 existuje jedina dvojica, ktorej je x kodom. Cislo 0 nie je kodom ziadnej dvojice.

Dohoda: vyraz p(x,y) budeme zapisovat ako x,y, pricom u,v,w znamena u,(v,w), teda zatvorkuje sa doprava. Operator , ma nizsiu prioritu ako + a -, teda u,v+w je to iste ako u,(v+w).

Poznamka: Funkcie splnajuce uvedene tri vlastnosti sa nazyvaju parovacie funkcie a existuje ich nekonecne vela. Jedna z nich je napriklad Cantorova parovacia funkcia c(x,y) = (x+y)(x+y+1)/2 + x+1 . Usporiadajme vsetky usporiadane dvojice prirodzenych cisel (x,y) podla suctu x+y, pricom dvojice s rovnakym suctom usporiadame podla prveho clena. Dostavame tak postupnost (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3)... Hodnota c(x,y) udava poradie dvojice (x,y) v tejto postupnosti. Lahko mozno overit, ze funkcia c splna vsetky uvedene vlastnosti.

Zoznamy. Zoznam cisel a(1), a(2), ... a(n) zakodujeme ako a(1),a(2),...,a(n),0=p(a(1),p(a(2),p(... p(a(n),0)...))). Kazde prirodzene cislo je kodom prave jedneho zoznamu, pricom 0 koduje prazdny zoznam a cislo x=u,v koduje zoznam, ktoreho prvym prvkom je u a v je kodom zoznamu ostatnych prvkov.

Pomocne premenne. V klauzule je mozne okrem vstupnych premennych pouzivat aj pomocne premenne. V priebehu vyhodnocovania klauzuly sa jednotlivym pomocnym premennym priraduju hodnoty. Pomocne premenne, ktore uz maju priradenu hodnotu, nazyvame ohodnotene. Ohodnotene premenne je mozne pouzit v lubovolnom vyraze v klauzule, rovnako ako vstupne premenne.

Vyhodnocovanie klauzul. Klauzula sa vyhodnocuje nasledujucim sposobom: Najprv sa priradia hodnoty vstupnym premennym. Potom sa postupne zlava doprava vyhodnocuje podmienka v pravej casti klauzuly, ktora ma tvar A1 and A2 and ... and An. Ai moze mat jeden z nasledujucich tvarov:

Ai ma tvar s<>t, s<t, s<= t, s>t, s>= t a vsetky premenne vo vyrazoch s a t su ohodnotene. Preto je mozne urcit hodnotu oboch vyrazov a porovnat ich.
Ai ma tvar s=t, pricom vsetky premenne v s aj t su ohodnotene. Postupuje sa rovnako ako v predchadzajucom pripade.
Ai ma tvar s=t, pricom vsetky premenne v s su ohodnotene a t obsahuje iba volania parovacej fukcie, neohodnotene pomocne premenne a konstanty. V tom pripade sa pomocnym premennym priradia take hodnoty, pri ktorych by platila rovnost s=t. Ak take hodnoty neexistuju (napr. 0=u,v), podmienka Ai sa povazuje za nesplnenu. Z vlastnosti parovacej funkcie vyplyva, ze ak take hodnoty existuju, daju sa hodnoty premennym priradit jednoznacne.

Ak nebolo mozne ohodnotit vstupne premenne klauzuly, alebo niektora cast podmienky nie je splnena, prerusi sa vyhodnocovanie klauzuly a pouzije sa ina klauzula funkcie. Ak je cela podmienka splnena, vyhodnoti sa vyraz nalavo od sipky a funkcia nadobudne jeho hodnotu.

Priklad: Funkcia Length pre zadany zoznam vrati ako vysledok jeho dlzku.

Length(x) = 0 & <- & x=0
Length(x) = 1 + Length(v) & <- & x=u,v

Vysvetlime si, ako prebehne vyhodnotenie funkcie Length pre vstup x = 7,0,0:

Length(7,0,0) = 1+Length(0,0) = 1+(1+Length(0)) = 1+(1+0) = 2

Funkcia bola zavolana s parametrom x=7,0,0, teda v definicii vyhovuje druha klauzula, pricom u=7 a v=0,0 (prva rovnost). Podobne vyhodnotenie prebehlo v 2. rovnosti, len u=v=0. V 3. rovnosti je parameter funkcie x=0, preto bola pouzita prva klauzula. Teraz su uz zname vsetky argumenty funkcie + a preto sa moze vyhodnotit konecny vysledok. Dlzka zoznamu 7,0,0 je teda 2.

Uloha: Vo funkcionalnom jazyku napiste

funkciu Rev, ktora zo vstupneho zoznamu x vypocita zoznam y, ktoreho prvky budu usporiadane presne v opacnom poradi. Napriklad Rev(1,3,2,4,7,0,0) = 0,7,4,2,3,1,0.
funkciu Append, ktora zo vstupnych zoznamov x a y vypocita zoznam z, ktory bude obsahovat postupne vsetky prvky zoznamu x a potom vsetky prvky zoznamu y, v povodnom poradi. Napriklad Append((1,2,3,0),4,5,0) = 1,2,3,4,5,0. Pozor - Append((1,2,3,0),4,5,0) <> (1,2,3),4,5,0 !
funkciu Order, ktora vzostupne usporiada zoznam cisel. Napriklad Order(1,3,2,4,7,0,0) = 0,1,2,3,4,7,0.

Poznamka: Nezabudnite na dokladny popis a zdovodnenie spravnosti vasho programu.

Poznamka 2: Snazte sa pisat svoje programy pomocou chvostovej rekurzie a tak, aby boli co najefektivnejsie (vzhladom k poctu volani funkcii). Najdolezitejsie vsak je, aby bol program spravny.

Podporte nás

Účet

Prihlasovanie už nefunguje. Používaj nový KSP web.

kontakt