- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 2. kola
Mili nasi riesitelia,
Blizia sa zimne prazdniny a aby ste sa pocas nich doma nenudili, prichadzaju k Vam nove zadania. Riesenia druheho kola nam posielajte do 7. januara 1999. Spolu s rieseniami nezabudnite poslat dvoj a trojkorunove znamky v celkovej hodnote 10.- Sk. Prajeme Vam vesele Vianoce a do noveho roku vela stastia, zdravia a tiez vela dobrych napadov pri programovani.
- O magickom symbole
- Ako Janko s Marienkou bytovu otazku riesili
- O bale
- Popularna prednaska
- O profesorovi Indigovi a vile Amalke II
1. O magickom symbole
Jedneho dna sa miestny kuzelnik Kin Lezuk vazne zamyslel. Potreboval totiz zistit, kolko najmenej dni mu potrva, kym aktivuje cely magicky symbol okolo dediny na ochranu pred temnymi silami. Magicky symbol je zlozeny z N magickych kamenov, ktore lezia na kruznici, ktorej stredom je dedina. Aktivacia prebieha nasledovne. Kin sa rano zobudi a vyda sa k niektoremu kamenu. Potom postupuje po kruznici cely den rovnakym smerom a zaklina vsetky magicke kamene po ceste. Po zakliati niekolkych kamenov sa vrati domov (cize ide od posledneho zakliateho kamena do dediny). Kin vsak moze putovat najviac H hodin denne, aby bol pred zotmenim doma. Aktivacia je ukoncena, ak zaklial kazdy kamen aspon raz (na poradi zaklinania jednotlivych kamenov nezalezi).
Uloha: Napiste program, ktory vypocita, kolko dni Kin potrebuje na aktivaciu kuzla. Vstupom programu bude pocet hodin H (maximalna doba trvania Kinovej cesty), pocet magickych kruhov N a dalej pre kazdy kamen cas, kolko trva cesta z dediny ku nemu, a kolko trva cesta od tohoto kamena do dediny. Taktiez pre kazde dva susedne kamene na kruznici dostane program cas cesty medzi nimi (jednym aj druhym smerom). Cas potrebny na zakliatie kamena je zanedbatelny.
Priklad:
Vstup:
H=3, N=3
Casy:
Tam Spat
------------------------------
dedina - kamen 1 | 1 3
dedina - kamen 2 | 2 1
dedina - kamen 3 | 2 1
kamen 1 - kamen 2 | 1 2
kamen 2 - kamen 3 | 1 2
kamen 3 - kamen 1 | 4 1
Vystup:Bude mu to trvat 2 dni.
2. Ako Janko s Marienkou bytovu otazku riesili
Iste si vsetci zivo pamatate na rozpravku o pernikovej chalupke. Ano, tak ako vy ste boli deti, aj Janko a Marienka boli deti a medzicasom vyrastli. Napriek tomu, ze sa doteraz poctivo zucastnuju kazdeho zbierania jahod a hadzania jezibaby do pece, nemaju si za co kupit byt. A tak raz, ked uz za jezibabou zatvarali na peci vratka, posepla Marienka Jankovi: "Janicko, ved je to celkom dobra chalupka, co keby sme sa tu zabyvali?" Nelenili teda a zacali opravovat svoj novy domcek, aby im nezatekalo (viete predsa, ze predtym z chalupky odlomili a zjedli niekolko pernikov). Marienka vyvalkala cesto a Janko vykrajoval rozne tvary. Uz mali takmer vsetko hotove a z cesta na doske zostali len zvysky, ked si vsimli, ze Janko zabudol vykrojit pernik na vetrak v tvare kruhu. Teraz sedia a dumaju, ci sa vobec kruh z tych zvyskov vykrojit da.
Napiste program, ktoreho vstupom je tvar zvysku cesta - N-uholnik zadany suradnicami svojich vrcholov zadanych postupne po obvode proti smeru hodinovych ruciciek, a rozmer vetraku - kruhu s polomerom r. Vystupom bude odpoved ano, ak sa kruhovy pernik da zo zvysku cesta vykrojit, alebo nie, ak sa neda.
Priklad:
Vstup:
Cesto je tvaru N=6-uholnika: (0,0), (3,1), (5,0), (3,2),
(3,4), (1,3)
Rozmer vetraku: r=1
Cesto je tvaru N=3-uholnika: (0,2), (8,0), (2,4)
Rozmer vetraku: r=2
Vystup:
ano
nie
3. O bale
Kde bolo tam bolo, za siedmimi horami a siedmimi dolami, kde sa voda sypala a piesok sa lial, bolo raz jedno kralovstvo...
V tomto kralovstve sa kazdorocne na kralovskom zamku konal velky ples. Pozvanych bolo mnoho hosti a nemalo dvojic si zahovorilo tanec. Prastara vestba vsak varuje, ze posledny bal nesmie mat viac tanecnych kol, ako je zlatych jablcok na kralovskej jabloni. S kazdym tanecnym kolom odpadne jedno jablcko a ak by sa tancovalo aj po spadnuti posledneho jablcka, krajinu by postihlo nestastie.
Kazdorocne sa stava predmetom spekulacii, ci sa podari splnit zelania vsetkych tanecnikov - teda, ci sa kazdej dvojici, ktora chce spolu tancovat, podari tancovat aspon jedno kolo. V tom istom kole moze tancovat lubovolne vela dvojic za predpokladu, ze kazdy pan tancuje najviac s jednou damou a kazda dama najviac s jednym panom.
Uloha: Je dany pocet zlatych jablcok na kralovskej jabloni p, dalej k - pocet dvojic, ktore si dohovorili tanec a jednotlive dvojice - vzdy najskor meno pana, potom meno damy. Zistite, ci je mozne uspokojit zelania vsetkych tancujucich a v pripade, ze to je mozne, vypiste lubovolny vyhovujuci rozvrh tancov. Mozete predpokladat, ze mena su jednoslovne.
Priklad:
Vstup:
p=3, k=7
Janicek Zlatovlaska
Bajaja Zlatovlaska
Bajaja Marienka
Popolvar Zlatovlaska
Bajaja Snehulienka
Janicek Marienka
Popolvar Snehulienka
Vystup:
ANO
1: Janicek Zlatovlaska, Bajaja Marienka,
Popolvar Snehulienka
2: Janicek Marienka, Bajaja Zlatovlaska
3: Popolvar Zlatovlaska, Bajaja Snehulienka
Vstup:
p=2, k=5
Janicek Zlatovlaska
Bajaja Zlatovlaska
Bajaja Marienka
Janicek Marienka
Popolvar Zlatovlaska
Vystup:
NIE
4. Popularna prednaska
Profesor Indigo sa vdaka svojmu novemu pocitacu stal slavnym a jeho prednasku na univerzite si zapisalo velmi vela studentov. Profesor od svojich studentov vyzadoval, aby chodili na vsetky prednasky a pri prichode sa zapisali do zoznamu pritomnych. Ako spravny informatik sa neobtazoval s nejakymi menami, ale hned na zaciatku roka ocisloval studentov cislami 1,2,... N a studenti do zoznamu zapisovali svoje cisla v dvojkovej sustave. Vsetko islo ako po masle, az raz na jednej prednaske jeden student chybal. Profesor si to hned vsimol a rozhodol sa, ze musi zistit, ktory to bol. Rozhodol sa napisat si program a kedze vila Amalka mala ten den prave dovolenku, musel pouzit normalny pocitac. Zoznam cisel studentov bol vsak velmi dlhy, preto sa mu ho nechcelo do pocitaca prepisovat cely.
Uloha: Napiste program, ktory nacita pocet vsetkych studentov N a potom bude klast profesorovi otazky typu "Zadajte i-ty bit (sprava) z j-teho cisla v zozname" (1<=j<N) a na zaklade odpovedi vypise cislo studenta, ktory nebol na prednaske. Mozete predpokladat, ze v zozname je binarny zapis kazdeho z cisel od 1 po N okrem jedneho. Ak ma j-te cislo menej ako i bitov, profesor zada 0. Snazte sa, aby vas program nekladol profesorovi prilis vela otazok.
Priklad:
Predpokladajme, ze N=3 a v zozname su cisla 11 a 1, ktore v desiatkovej
sustave zodpovedaju 3 a 1. Chyba teda cislo 10 (2). Praca programu moze
vyzerat napriklad takto:
Zadajte N
> 3
Zadajte 1. bit (sprava) z 1. cisla v zozname
> 1
Zadajte 1. bit (sprava) z 2. cisla v zozname
> 1
Vysledok je 10
5. O profesorovi Indigovi a vile Amalke II
Profesor Indigo zostavil svoj novy pocitac "PP Amalka inside" (popisany v zadaniach prveho kola) hlavne preto, lebo sa mu zdalo, ze to zjednodusi a skrati mnohe programy. Zistil vsak, ze tento pocitac ma aj dalsiu vyhodu - mnohe vypocty trvali ovela kratsie ako na beznom pocitaci. Aj to umoznuju to obdivuhodne schopnosti vily Amalky:
V pripade, ze pre dany vstup neexistuje postupnost vetveni choose, ktora vedie k prikazu accept, vila to zisti hned na zaciatku, takze samotny pocitac vobec nemusi prevadzat ziadne vypocty. Ak je teda odpoved nie, cas vypoctu je 0. V pripade, ze odpoved je ano, vypocet prebehne a vila zvoli v kazdom prikaze choose taku vetvu, ze dovedie vypocet k prikazu accept. Postupnosti vetveni, ktore vedu k prikazy accept vsak moze byt viacero a mozu sa velmi lisit dlzkou zodpovedajuceho vypoctu. Vila Amalka sa vsak vdaka svojej vynikajucej intuicii vzdy rozhodne tak, aby bol vypocet najkratsi mozny.
Uvazujme napriklad program, ktory bol uvedeny v zadaniach prveho kola. Ak pre dany vstup neexistovala cesta z policka [0,0] na policko [n-1,n-1] iduca iba po nulach, tak vypocet trval nulovy cas. V opacnom pripade bol cas vypoctu umerny dlzke najkratsej cesty po nulach medzi tymito dvoma polickami. Pre niektore rozmiestenia nenulovych prvkov sa vsak moze stat, ze dlzka najkratsej cesty bude priblizne (n^2)/2, casova zlozitost programu je O(n^2) aj na pocitaci "PP Amalka inside".
Dobry priatel profesora Indiga, doktor Jones, je archeolog. K jeho najnovsim uspechom patri nalez vzacneho papyrusoveho zvitku, ktory patril hlavnemu spravcovi ciest Nacestejamasovi. Tento papyrus obsahuje zoznam vsetkych ciest v krajine. Kazda cesta v zozname spajala dve mesta. Tento zoznam je o to cennejsi, ze je to prva pisomna zmienka o mnohych mestach. Bohuzial, vsetky nazvy miest v papyruse boli doktorovi Jonesovi uplne nezname. Rozhodol sa, ze zoznam porovna s najstarsou dostupnou mapou krajiny. Dufa, ze sa mu takto podari urcit, akym mestam zodpovedali nazvy na papyruse. Doktor Jones vychadzal z tychto predpokladov:
- Kazde mesto, ktore je spomenute v Nacestejamasovom papyruse, sa nachadza aj na mape, na mape vsak mozu byt aj dalsie mesta, ktore vznikli neskor ako papyrus.
- Nove mesta mohli vznikat bud na uz existujucej ceste, v tom pripade vznikajuce mesto rozdelilo cestu, na ktorej vzniklo, na dve cesty; alebo mimo cesty. Cesty mohli vzniknut medzi lubovolnou dvojicou miest.
- Kazda cesta, uvedena v papyruse je aj na mape; mohla byt vsak rozdelena pri vzniku miest na niekolko casti.
- Medzi ziadnou dvojicou miest nevedie nikdy viac ako jedna cesta.
Uloha: Ocislujme mesta na mape 1,...,Mm a nazvy miest v papyruse ocislujme 1,... ,Mp. Napiste program pre "PP Amalka inside", ktory na vstup dostane pocet miest na mape Mm a pocet ciest na mape Cm, pocet miest na papyruse Mp a pocet ciest na papyruse Cp ako aj zoznamy ciest na mape a na papyruse (kazda cesta je urcena pociatocnym a koncovym mestom). Program ma zistit, ci je mozne kazdemu cislu mesta z papyrusu priradit cislo mesta na mape, tak aby toto priradenie splnalo Jonesove predpoklady. Presnejsie, vas program ma mat hlavicku
const MAX = 1000;
type cesta = record z,k : integer; end;
zoznam_ciest = array[1..MAX] of cesta;
program Jonesova_mapa(Mm,Cm,Mp,Cp : integer; ZCm,ZCp : zoznam_ciest);
Vas program ma teda dat odpoved ano (za vydatnej pomoci vily Amalky) prave
vtedy, ak existuje zodpovedajuce priradenie miest na mape miestam na
papyruse. Ak taketo priradenie neexistuje, program ma dat odpoved nie.
Skuste tiez odhadnut casovu zlozitost vasho programu na pocitaci "PP Amalka
inside".
Priklad:
Vstup:
Mm = 5; Cm = 5; Mp = 3; Cp = 3
ZCm = ((1,2),(2,3),(3,4),(4,1),(2,5))
ZCp = ((1,2),(2,3),(1,3))
Vystup:
Pre takyto vstup ma dat "PP Amalka inside" vystup ano. V tomto
pripade existuje viacero moznych priradeni, napriklad mestu 1 z papyrusu
priradime mesto 3 z mapy, mestu 2 z papyrusu priradime mesto 4 a mestu 3 z
papyrusu priradime mesto 1.
1998, Organizers of the CSP
