KSP.sk

Korešpondenčný seminár z programovania

Priklady 3. kola

Mili nasi riesitelia,

iste ste si vsimli, ze sme sa prave dostali do druhej polovice tohto rocnika nasho seminara. Tym, ktori s nami vydrzali az doteraz, srdecne blahozelame, ostatnych od nas pozdravte. Svoje riesenia 3. kola nam posielajte do 9. marca 1998. Uz sa na ne tesime. A nezabudnite na znamky! Kto ich este neposlal, nech sa poponahla (inak nedostane vzorove riesenia). Este Vam chceme pripomenut:

Aj po obede si umyvajte zuby! Nech sa vam nehnusia...

KSPaci

  1. O zlej kralovnej
  2. O eskimakoch a iglu
  3. O velkom smade
  4. O vianocnych darcekoch
  5. O funkcionalnom programovani III

1. O zlej kralovnej

"Zrkadielko, zrkadielko, povedz ze mi, ktora zo zien najkrajsia je tu na Zemi?" pytala sa zrkadielka navonana, naondulovana a nasminkovana kralovna, osperkovana od hlavy po paty.

"Tu na hrade vokol teba nenajde sa krajsia deva, no za horami, dolami, krajsia Snehulka medzi trpaslikmi," odpovedalo zrkadielko. A nazlostila sa kralovna, to zrkadielko ju urcite klame. Ved Snehulku sama zahrdusila. A v hneve kralovna zrkadielko rozbila. Coskoro vsak zacala trpko lutovat svoj cin - tej nehanebnici sa uz predsa podarilo uniknut, co ak zase...

A rychlo si nechala doniest nove zrkadlo, to vsak bolo volajake hlupe. Radcovia radili, radili a poradili, ze ho treba naprogramovat. Pomozte kralovnej a naprogramujte zrkadielko.

Uloha: Zrkadielko naprogramujte tak, aby stale prijimalo spravy a odpovedalo na otazky (az do skonania sveta).

Na vstup prichadzaju od sudiciek spravy o narodeni, z marnic spravy o smrti jednotlivych zien, sprava o skonceni roka a otazka, ktora zo zien je najkrajsia. Spravy maju nasledujuci tvar:

  • NARODENIE <meno> <index> <rozkvet>, kde <meno> je meno novonarodenej, <index> je pociatocny index krasy (realne cislo), tento sa kazdy rok na Silvestra zvysi o 1, az kym nedosiahne vrchol - pocas roka, ked zena dosiahne <rozkvet> rokov, potom sa bude kazdy rok o 1 zmensovat
  • EXITUS <meno>, kde <meno> je meno zosnulej
  • SILVESTER
  • ZRKADIELKO, ZRKADIELKO POVEDZ ZE MI, KTORA ZO ZIEN NAJKRAJSIA JE NA ZEMI. Ak najkrajsia zo zien je KRALOVNA, tak zrkadielko odpovie CO BYS' PRESLA SIRY SVET, KRAJSEJ DEVY NIKDE NIET. Ak kralovna nie je najkrajsia, ale najkrajsia je <kraska>, vypise TU NA HRADE VOKOL TEBA NENAJDE SA KRAJSIA DEVA, NO ZA HORAMI, DOLAMI KRAJSIA JE <kraska>. Mozete predpokladat, ze stale je prave jedna zo zien najkrajsia. Ak nie je ziadna zena v zozname (teda ani na Zemi), vypise VSETKY ZENY POMRELI

Ked sprava pre zrkadielko nebude mat ziaden z predchadzajucich tvarov, zrkadielko odpovie TVOJA REC MI ZNIE AKO BZUKOT MUCH.

2. O eskimakoch a iglu

Ako iste vsetci vieme, aj eskimaci maju svoje osady, kde si pokojne ziju, stavaju iglu, chytaju ryby a celkovo sa maju fajn. Este donedavna si eskimaci z jednej osady budovali vsetky iglu do radu a cesticka spajala len susedne domky. Bolo to vyhovujuce, lebo sa dalo z kazdeho iglu dostat do kazdeho ineho iglu a ked si niekto postavil novy pribytok na koniec zastavby, stacilo vyslapat len kratku vzdialenost k nemu.

Ale teraz, po nastupe Velkeho Eskimaka, sa mnohe zmenilo. Velky Eskimak si nechal postavit Velke Iglu v kazdej osade a vyslapat k sebe cestu od vsetkych ostatnych pribytkov z osady. Ked vsak zistil, ze vyslapane cesticky rychlo znovu zafuka a ich stala udrzba je aj pre neho pomerne draha, rozhodol sa presne stanovit, ktore cesty sa budu v ktorej osade udrziavat. V kazdej osade z uz vyslapanych ciest vybral take, aby sa dalo z kazdeho iglu dostat do kazdeho, ale aby nebola ziadna cesta nadbytocna (teda aby sa nedalo z jedneho iglu do druheho prejst dvoma roznymi sposobmi). Navyse sa snazil svoj vyber ciest urobit tak, aby pohlad z lietadla na dve rozne osady vyzeral rozne. Zacala ho ale trapit myslienka, ci sa to vobec da...

Uloha: Napiste program, ktory pre zadany pocet iglu N v osade (napriek nazoru Velkeho Eskimaka, ze jeho Iglu je za tri, budeme ho pocitat iba raz) vypocita, kolkymi sposobmi sa daju navrhnut udrzovane cesty.

Priklad:
Pre N=4 je to 8 sposobov.

3. O velkom smade

Velka piesocna krajina je pomerne riedko obyvana. Vsetky osady domorodcov lezia pri Malej piesocnej rieke - jedinej rieke v krajine. Caste pieskove burky velmi stazuju pestovanie rastliny butu, znamej svojimi pozoruhodne velkymi plodmi, z ktorych miestni obyvatelia tradicne pripravuju opojny napoj lavorovicu. Pocet plodov butu, ktore preziju do najblizsieho zberu urody, sa stava predmetom ostrych sporov. To vyuzivaju rozni pokutni vestci a predpovedaci buducnosti. Za mensi ci vacsi poplatok su ochotni nechat sa ponuknut lavorovicou a potom v tranze vykrikovat vestby typu "Prve styri osady ponize Jamy v piesku dole prudom Piesocnej rieky budu mat urodu minimalne osemdesiattri plodov butu" alebo "Co by si splavil Piesocnu rieku od Piesocneho vrchu po Kopu piesku, viac nez patdesiatsedem plodov butu nenajdes".

Jeden takyto vestec bol domorodym obyvatelom velmi podozrivy. Na to, aby ho mohli natriet kuracou krvou, vyvalat v peri a zakopat po krk do piesku, musia mu najprv dokazat, ze aspon raz klamal. I spisali si vsetky jeho vestby na papier a teraz nad nimi sedia a nevedia, co dalej.

Uloha: Ocislujme osady dole prudom Piesocnej rieky 1,...,n. Vsetky vestby su tvaru "v osadach k, k+1,... ,l sa spolu urodi aspon m plodov butu" alebo "v osadach k, k+1,... ,l sa spolu urodi najviac m plodov butu". Napiste program, ktory nacita pre kazdu vestbu trojicu cisel k,l,m (k<= l) a typ vestby a zisti, ci je mozne, aby sa vsetky splnili.

Priklad:
Vstup:
3 vestby: 

1 2 aspon 26
3 3 aspon 15
1 3 najviac 40
Vystup:
Vsetky vestby sa nemozu splnit.

4. O vianocnych darcekoch

Frutus a Brutus sa i tento rok zisli cez vianocne sviatky doma. Vianocna pohoda panovala vsade navokol, pod stromcek dostali obaja navlas rovnake darceky, aby sa nemohli hadat a handrkovat o to, koho darcek je hodnotnejsi. Ale ked to vsetko porozbalovali, nastal problem, ktory by nikto neocakaval. Obom zostali po darcekoch identicke kopy skatul. Vtedy prislo Frutovi na um, ako dokazat, ze je sikovnejsi. Zacal z tychto skatul stavat vezu. Brutus sa nedal a onedlho mal aj on skatule poukladane na sebe. Pravidla boli jasne: poukladat jednotlive skatule na seba tak, aby veza bola najvyssia mozna. Iba tak sa dalo vyhrat. Vzdy, ked sa jednemu podarilo ziskat urcitu vysku, druhy prisiel s konkurencnym rozostavenim skatul, tvoriacim vyssiu vezu. A pravdepodobne kombinuju az dodnes, lebo nevedia zistit, aka najvyssia veza sa vobec da postavit.

Uloha: Napiste program, ktory pre zadane N - pocet skatul a rozmery - (x[1],y[1],z[1]),...,(x[n],y[n],z[n]) vypise najvacsiu moznu vysku veze, ktora sa da z danych skatul postavit. Skatule sa daju lubovolne otacat. Ak je skatula B polozena na skatuli A, pricom horna stena A ma rozmery a1, a2 (a1<= a2) a dolna stena B ma rozmery b1, b2 (b1<=b2), potom musi platit a1<=b1 a a2 <=b2.

Priklad:
Vstup:
N=3
Rozmery skatul: (2,2,2), (3,2,1), (1,2,2)
Vystup:
Maximalna vyska je 7.

5. O funkcionalnom programovani III

V priklade budeme pracovat s funkcionalnym jazykom opisanym v zadaniach prveho a druheho kola. Tam sme sa naucili pracovat s klauzami nad prirodzenymi cislami a kodovat do prirodzenych cisel datovu strukturu zoznam. Velmi prirodzenym sposobom mozno pomocou zoznamov reprezentovat strukturu stromu. V tomto priklade budeme uvazovat tzv. binarne stromy. Prazdny binarny strom neobsahuje ziaden vrchol. Neprazdny binarny strom obsahuje prave jeden vrchol, do ktoreho nevchadza ziadna hrana - koren. Z korena vychadzaju dve hrany, ktore ho spajaju s lavym a pravym podstromom (v pripade, ze tento podstrom nie je prazdny, hrana vedie do jeho korena). V kazdom vrchole nasho binarneho stromu je ulozene prirodzene cislo.

Binarny strom. Prazdny binarny strom reprezentujeme prazdnym zoznamom 0. Neprazdny binarny strom T s hodnotou k v koreni, s lavym podstromom TL a pravym podstromom TP reprezentujeme ako zoznam z(T) = (k,z(TL),z(TP)), kde z(TL) je zoznam reprezentujuci strom TL a z(TP) je zoznam reprezentujuci TP.

Hlbka stromu. Hlbku stromu definujeme vo funkcionalnom jazyku pomocou funkcie Depth.

Depth(zT)=0 <- zT=0
Depth(zT)=Depth(zTL)+1 <- (zT=k,zTL,zTP) and (Depth(zTL)>Depth(zTP))
Depth(zT)=Depth(zTP)+1 <- (zT=k,zTL,zTP) and (Depth(zTL)<=Depth(zTP))

Priklad. Strom na obrazku 1 je reprezentovany zoznamom (1,(2,(3,0,0),(4,0,0)),(5,(6,0,0),0)), strom na obrazku 2 zoznamom (4,(1,0,(2,0,0)),(7,(6,0,0),0)).

Vyhladavacie stromy. Binarny strom sa nazyva vyhladavaci, ak pre kazdy jeho podstrom T s korenom vo vrchole v plati, ze hodnota vo vrchole v je vacsia ako najvacsia hodnota z laveho podstromu stromu T a zaroven je mensia ako najmensia hodnota z praveho podstromu stromu T.

Napriklad strom na obr. 1 nie je vyhladavaci, pretoze kazdy lavy syn ma hodnotu vacsiu ako otec. Naopak strom na obr. 2 vyhladavaci je.

Vo vyhladavacich stromoch mozno lahko zistit, ci je v nom zaradeny dany prvok - na zaklade hodnoty korena mozno totiz jednoznacne urcit, v ktorom podstrome sa hladany prvok moze nachadzat. Istym zlepsenim su vyvazene vyhladavacie stromy - u nich podstromy kazdeho vrchola maju priblizne rovnaku velkost, a teda kazdym porovnanim vylucime polovicu moznosti.

AVL-stromy. Binarny vyhladavaci strom nazveme AVL-stromom, ak sa hlbky laveho a praveho podstromu kazdeho vrchola lisia najviac o 1.

Strom na obr. 2 je AVL-stromom, pretoze sa hlbky oboch podstromov pre kazdy vrchol okrem vrcholov s cislami 1 a 7 rovnaju. Lavy podstrom vrchola s cislom 1 ma hlbku 0 a pravy 1, teda ich rozdiel je rovny prave jednej. Podobne rozdiel hlbok laveho a praveho podstromu vrchola s cislom 7 je jedna.

Uloha: Vo funkcionalnom jazyku napiste

  1. funkciu Member(T,x), ktora vrati 0, ak sa v AVL-strome T nenachadza vrchol s hodnotou x, alebo 1, ak sa tam vrchol s uvedenou hodnotou nachadza.
  2. funkciu Insert(T,x), ktora zo vstupneho AVL-stromu T a prvku x vypocita AVL-strom T', ktory bude obsahovat vrcholy s rovnakymi cislami ako strom T a navyse vrchol s cislom x. Mozete predpokladat, ze strom T vrchol s cislom x neobsahuje. Napr. Insert((1,0,(2,0,0)),3) = 2,(1,0,0),(3,0,0).
  3. funkciu Delete(T,x), ktora zo vstupneho AVL-stromu T a prvku x vypocita vyhladavaci AVL-strom T', ktory bude obsahovat vrcholy s rovnakymi cislami ako strom T okrem vrchola s sislom x. Mozete predpokladat, ze strom T vrchol s cislom x obsahuje. Napr. Delete((4,(1,0,(2,0,0)),(5,0,0)),5) = 2,(1,0,0),(4,0,0).

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

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

1998, Organizers of the CSP
Podporte nás

Účet

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

Redirecting