- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Priklady 1.kola 18.rocnika KSP
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 23. oktobra 2000. Predtym, ako nam poslete svoje riesenia prveho kola, nezabudnite si pozorne precitat propozicie. Zbadate v nich niekolko dolezitych zmien. Spolu s rieseniami nam poslite vyplneny evidencny listok a znamky v celkovej hodnote 15,- Sk.
KSPaci
1. O vybijanej
V Nalomenej Trieske sa uskutocnil kazdorocny turnaj vo vybijanej. Zucastnilo sa ho tolko druzstiev ako snad este nikdy, ba dokonca az hen z Dolneho Kelcova jedno prislo. Odohrali sa stretnutia systemom kazdy s kazdym, organizatori si zaznacili vysledky (Pre tych, co vybijanu v zivote nehrali - v kazdom zapase jedno druzstvo vyhralo a to druhe logicky prehralo) a nastali problemy. Sef organizacneho vyboru Kleofas sa totiz zhacil. "Co len budeme robit ? Zabudli sme si znacit skore a teraz sa nam lahko moze stat, ze niektore dve muzstva budu na tom istom mieste. Ale ktore potom dostane ktoru cenu ?" Vsetci sa hlboko zamysleli a vysledok sa hned dostavil. "Mam to!" zaradoval sa Zacharias. "Ved my sme vlastne nikdy nevyhlasili, ako budeme turnaj hodnotit! Keby sa nam podarilo druzstva zoradit tak, ze kazdy prehral s tym, kto je o jedno miesto pred nim, nik by sa nemohol stazovat a vsetko by bolo v poriadku!" No vlna nadsenia coskoro opadla, ked zistili, ze najst take poradie vobec nie je jednoduche.
Uloha
V poli Vys[1..N,1..N]} su dane vysledky turnaja, pricom ak druzstvo i vyhralo nad druzstvom j, Vys[i,j]=1, v opacnom pripade Vys[i,j]=0. Napiste program, ktory vypise jedno mozne poradie druzstiev d1,...,dN take, ze pre vsetky i, 1 <= i < N druzstvo di vyhralo nad druzstvom di+1, pripadne Smola, ak take poradie neexistuje.
Priklad
Vstup0 0 1 1 0 1 0 0 0
Vystup
2,1,3
2. O prepustani v TSSL
TSSL (Top Secret Scientific Laboratory) patri medzi najvacsie centra vedeckeho vyskumu. Avsak ani v TSSL este nevynasli strom, na ktorom rastu peniaze, a preto sa aj tam muselo pristupit k operacii s krycim menom PPP (prepustanie prebytocnych pracovnikov). No a za obet padli tentokrat vedci.
Momentalne ma kazdy vedec prideleny presne jeden projekt. To je, pravdaze, velke plytvanie, lebo niektori vedci by zvladli aj viac projektov, a tak by mohli byt nejaki ini prepusteni. Take jednoduche to vsak nie je, lebo aj vedci su len ludia a neslobodno ich pretazovat (taky projekt nie je len tak hocico, projektu treba venovat vela - prevela casu). Podla internej vyhlasky 355/113 ma vedec obmedzenu pracovnu dobu. A aby to este nebolo vsetko, z dovodov udrzania vysokeho stupna utajenia a bezpecnosti nesmie ziaden vedec pracovat na viac ako dvoch projektoch (co keby utiekol s vysledkami k nepriatelovi?)
Uloha
Dany je aktualny pocet vedcov N a ich maximalna pracovna doba M. Dalej je pre kazdy z N projektov dana jeho casova narocnost, pricom projekty su na vstupe podla nej usporiadane zostupne. Napiste program, ktory vypocita maximalny pocet vedcov, ktorych mozno prepustit za dodrzania vsetkych nariadeni. Taktiez nech vypise lubovolne pripustne rozdelenie projektov medzi zvysnych (neprepustenych) vedcov.
Priklad
VstupN=6 M=50 Projekty: 44 29 26 25 10 8
Vystup
Vedec #1: 6,2 Vedec #2: 5,3 Vedec #3: 4 Vedec #4: 1 Ostatnych (2) vedcov mozno prepustit.
Poznamka
Uvedeny vystup nie je nutne jediny spravny.
3. O najkratsom tuneli
Nebezpecneho zlocinca medzinarodneho formatu Viliama Branu konecne zatkli a posadili, kam patri - do prisne strazeneho vazenia na ostrov Alcatraz. Ludia z blizkeho i sirokeho okolia si vydychli. Vydychli si dokonca aj Viliamovi lenivi kumpani, ktori dufali, ze po dlhych rokoch driny si konecne dopraju trocha oddychu. No ich radost netrvala dlho. Z hrozou totiz zistili, ze zabudli kombinaciu od Viliamovho trezoru, kde bol ulozeny cely ich spolocny majetok. Preto sa rozhodli, ze Viliama musia dostat na slobodu.
Viliamovi kumpani sa preplavili na ostrov, ktory je k Alcatrazu najblizsie. Aby vyslobodili svojho sefa, rozhodli sa vykopat tunel, ktory by spajal ostrov, na ktorom sa nachadzaju, s ostrovom Alcatraz. No kedze nie su privelmi usilovni, velmi im zalezi na tom, aby bol vykopany tunel najkratsi mozny. A tak teraz smutne sedia nad mapou oboch ostrovov a premyslaju, ako tunel vykopat. Je to vsak uloha nad ich sily, a preto im budete musiet pomoct vy.
Uloha
Su dane cisla N a M. Dalej je dany N-uholnik, ktory reprezentuje obrys ostrovu Alcatraz a M-uholnik, ktory reprezentuje obrys ostrova, na ktorom sa nachadzaju Viliamovi kumpani. Oba mnohouholniky su dane vymenovanim suradnic svojich vrcholov v smere hodinovych ruciciek, nemusia byt konvexne ani disjunktne. Napiste program, ktory vypocita najkratsiu moznu dlzku tunela, ktory spaja oba ostrovy (t.j. dlzku najkratsej usecky, ktorej jeden krajny bod lezi v prvom mnohouholniku a druhy krajny bod lezi v druhom mnohouholniku).
Priklad
Vstup 1
N=5 M=3 (1,1), (3,1), (2,2), (3,3), (1,3) (3,2), (4,3), (4,1)
Vystup 1
Najkratsia mozna dlzka tunela je 0.707.
Vstup 2
N=4 M=4 (1,0), (2,1), (1,2), (0,1) (2,0), (3,1), (2,2), (1,1)
Vystup 2
Najkratsia mozna dlzka tunela je 0.
4. O slepacej farme
V Stuchaniciach pri Koryte v ramci celonarodneho boja proti nezamestnanosti zalozili slepaciu farmu. A keby len to, dokonca este aj nejake sliepky kupili. Nuz a ako ano, ako nie, urodilo sa im uz onedlho na nej prvych par vajicok. A pomerne rychlo vyrastli. Vecer nic a rano... "Hla! Vajicka!" zbehla sa hned cela dedina. "Tie su urcite najkrajsie v kraji. Ba co, na svete!" prekrikovali sa. "A urcite aj najlepsie!" "A urcite aj najpevnejsie..." poznamenal sused Zavis, ktory mal zlu naladu, lebo v jeho kravine sa za celych pat rokov ani jedno vajicko neurodilo.
"Ano, ano!" kricali dedincania, no potom sa zarazili. Ze su najkrajsie, to na nich vidiet na prvy pohlad. Ale ako zistia, ci su najpevnejsie? "To je lahke." poucil ich Zavis. "Pevnost vajicka sa meria tak, ze je to najvyssia vyska v centimetroch, z ktorej pad vajicko prezije bez toho, aby sa rozbilo." A tak dedincania zobrali urodu a zacali merat. Len sused Zavis sa oprel o plot a pozoroval so skodoradostnym vyrazom v tvari, ako Gejza zdrapil prve vajicko, pustil ho z vysky N cm a to po kratkom lete dopadlo na zem a rozbilo sa na marne kusky.
Uloha
Napiste program, ktory nacita N - vysku, z ktorej sa uz vajicko urcite rozbije a M - pocet zvysnych vajicok. Potom bude postupne pisat vysky v centimetroch, z ktorych maju dedincania pustit vajicko a z klavesnice zakazdym nacita, ci sa vajicko rozbilo alebo nie. Kedze dedincania su netrpezlivi, treba, aby vas program (v najhorsom pripade) potreboval co najmenej spusteni vajicka. Nezalezi na tom, kolko vajicok pocas hladania kritickej vysky vas program rozbije. Samozrejme, po rozbiti posledneho vajicka uz musi hladanu vysku vediet.
Priklad
N=10 M=2 Spust z vysky 1 cm > nerozbilo sa Spust z vysky 3 cm > nerozbilo sa Spust z vysky 5 cm > rozbilo sa Spust z vysky 4 cm > nerozbilo sa Vajicka sa rozbiju pri spusteni z vysky 5 cm a viac. (Na zistenie bolo treba 4 spustenia.)
Poznamka
Zdovodnite, preco vas program vzdy spravne urci kriticku vysku a skuste spocitat, kolko skokov potrebuje v najhorsom pripade pre dane M a N.
5. O Santolande I
Jedneho pekneho letneho dna si zlatokop Santo zmyslel, ze je na zlatokopectvo stary. A pri tej prilezitosti sa rozhodol zalozit zabavny park pre zlatokopov - Santoland.
Najvacsou atrakciou Santolandu ma byt bludisko, takzvana Rumova jaskyna. Rumova jaskyna pozostava z N komor, pre jednoduchost ocislovanych 1 az N. Medzi komorami je mnozstvo uzkych tunelov (do kazdeho sa na sirku zmesti len jeden zlatokop). Aby nedochadzalo k zrazkam zlatokopov v tuneloch, Santo do kazdeho tunela nakreslil sipku, ktorym smerom sa v nom ma ist. A aby vsetci videli, ze sa konecne naucil citat a pisat, na zaciatok kazdeho tunela napisal nejake pismeno. No a nakoniec vybral niekolko komor a v kazdej ukryl flasu rumu.
Len co Santo dokoncil pripravy, prisli prvi navstevnici. Santo dal kazdemu z nich papierik, na ktory napisal akusi postupnost pismen a povedal:
"Mozete vstupit do Rumovej jaskyne. Mozete sa po nej prechadzat ako len chcete. Ale kto by z pokladov Rumovej jaskyne ochutnat chcel, tieto pravidla dodrziavat musi:
- V komore c. 1 svoju put zacne.
- Predpisane smery v tuneloch dodrziavat bude.
- Len do takeho tunela vojde, na zaciatku ktoreho rovnake pismeno ako prve nevyskrtnute pismeno na papieriku je. Po prejdeni tunela toto pismeno z papiera vyskrtnut sa musi.
- Ak ziadny tunel z komory na pozadovane pismeno nevedie, zlatokop sa s hanbou z jaskyne domov pobrat musi.
- Komu uz ziadne pismeno na papieriku nezvysilo, v komore, v ktorej sa prave nachadza, flasu rumu vyhladat moze."
Zlatokopi sa naskutku aj s papierikmi rozprchli po jaskyni flase rumu hladat. Po par hodinach bludenia vsak zistili, ze najst podla papierika tu spravnu komoru vobec nie je jednoduche. Problem je totiz v tom, ze z niektorych komor vedie na jedno pismenko viacero tunelov, takze nie je jasne, ktorym smerom sa treba vydat. Nuz sa zlatokopi stretli, dali hlavy dokopy a radili sa, co dalej. Napadlo ich, ze im Santo mohol dat papieriky, podla ktorych sa vobec neda do komor s rumom prist. Aj by Santa zbili, ale najprv si chcu byt nacistom, ze ich oklamal. Na to vsak budu potrebovat vasu pomoc.
Uloha
Napiste program, ktory nacita pocet komor N, popis tunelov (kazdy tunel je urceny cislom zaciatocnej a koncovej komory a pismenom napisanym na jeho zaciatku), cisla komor, v ktorych je ukryty rum a postupnost pismen napisanych na papieriku a rozhodne, ci existuje trasa podla Santovych pravidiel (t.j. zacinajuca v komore 1, prechadzajuca tunelmi oznacenymi rovnakymi pismenami a v rovnakom poradi ako na papieriku), ktora konci v nejakej komore s rumom. Trasa moze prechadzat viackrat cez tu istu komoru. Nezalezi pritom na tom, ci trasa prechadza cez nejake komory s rumom, dolezite je len to, v ktorej komore konci.
Priklad
Vstup
N = 4 tunely: 1 3 a 1 4 b 2 1 a 2 3 a 3 4 b 4 2 b 4 3 a komory s rumom: 2, 4 papierik: abbababb
Vystup
Da sa. (Jedna trasa vedie cez komory 1, 3, 4, 2, 3, 4, 3, 4, 2, ina cez 1, 3, 4, 2, 1, 4, 3, 4, 2).
(c) 3. september 2000, webmaster
