Priklady 1. kola

Mili priatelia KSP,

pred sebou mate zadania prveho kola "ostrej" kategorie KSP. Okrem tejto kategorie, ktora bude, rovnako ako doteraz obsahovat najma tazsie priklady, organizujeme aj kategoriu Z. Podmienky pre ucast v tejto kategorii ako aj ostatne potrebne informacie najdete v propoziciach seminara. Radime vam poriadne si ich precitat, usetrite sebe aj nam kopu starosti. Dufame, ze sa vam bude KSPecko pacit a ze nam aj nadalej zachovate vasu priazen.

Vase riesenia nam posielajte na horeuvedenu adresu (heslo KSP) a to do 21. oktobra 1996 (rozhoduje peciatka na obalke).

Na dobru polievku najdu sa hostia,

KSPaci

O tybloni
O dlhociznych dazdovkach
O naladenej strune
The Streets of San Benatky
O Stevovej sieti

1. O tybloni

V Nalomenej Trieske rastie cudesna tyblon. Ak ste takyto strom este nevideli, nevadi, ani my. Trabantovka povedala, ze jeho plodmi su pochopitelne tyblka. Tyblko vyzera skoro ako onblko, ibaze je dvojrozmerne, teda ma tvar lubovolneho mnohouholnika, ktory ma v kazdom vrchole male modre nic (ked je tyblko zrele). Kedze kazde tyblko je ine, pri jeho rozdelovani nastavaju problemy. Treba ho totiz rozdelit tak, aby pri rezani vznikli len casti trojuholnikoveho tvaru, pricom v kazdom vrchole takehoto trojuholnika je male modre nic (v opacnom pripade moze pri konzumacii vzniknut neprijemna alergicka reakcia).

Uloha: Napiste program, ktory pre dany mnohouholnik vytvori jeho lubovolnu triangulaciu. Triangulacia je take rozdelenie mnohouholnika na neprekryvajuce sa trojuholniky, ze vrcholy kazdeho trojuholnika su vrcholmi mnohouholnika. Mnohouholnik je zadany poctom vrcholov N a vymenovanim suradnic jeho vrcholov po obvode proti smeru hodinovych ruciciek. Vystup programu bude pozostavat zo zoznamu vytvorenych trojuholnikov.

Priklad Vstup:
N=5
[0,0],[2,2],[1,2],[2,3],[0,3]
Vystup:
([0,0],[2,2],[1,2])
([0,0],[1,2],[0,3])
([1,2],[2,3],[0,3])

2. O dlhociznych dazdovkach

Jezkovia to mali vzdy jednoduche. Ked sa chceli zmestit do maleho priestoru, proste sa schulili do klbka. Dazdovky to maju omnoho tazsie. Vedia sa totiz zohybat len vo svojich "klboch", ktore maju medzi clankami. Nastastie dazdovky su dost sikovne - vedia sa dokonca zohnut v klbe tak, ze ich clanky sa spatne prekryju...

Uloha: Napiste program, ktory pre zadane dlzky clankov dazdovky zisti, na aku minimalnu dlzku sa moze dazdovka poskladat. Dazdovka je priamka, ktora pri poskladani moze byt v klboch ohnuta o 0, alebo o 180 stupnov. Clanky dazdovky po sebe nasleduju v takom poradi, v akom su na vstupe zadane.

Priklad: Vstup:
Pocet clankov=5
Dlzky clankov=1,3,2,3,2

Vystup:
Dlzka poskladanej dazdovky je 4.

3. O naladenej strune

Usilovny Tomas si nechal za tazke peniaze naladit klavir. Kedze ladic byva az hen za lesom, musel si Tomas klavir dotlacit spat do brlozka sam. Aby sa klavir nerozladil, nesmie nim Tomas otacat - odstrediva sila posobiaca pri takomto pohybe na struny by ich natiahla a klavir by bol znovu rozladeny.

Kazdy z vas uz iste aspon raz v zivote tlacil klavir lesom a preto si viete predstavit, co to znamena. Lepsie je si najskor zistit, ci sa vobec klavir lesom pretlacit da. Les je zo severu aj z juhu ohraniceny dvoma riekami, ktore tecu tesne pri najsevernejsom a pri najjuznejsom strome lesa. Chudak Tomas teda potrebuje zistit, ci moze klavir presunut z vychodu na zapad (bez otacania).

Uloha: Napiste program, ktory pre zadany pocet stromov, ich suradnice a rozmery klavira (obdlznika) vypise, ci je mozne dany klavir lesom preniest. Klavir je na zaciatku na hony vzdialeny od lesa a hrany jeho kolmeho priemetu na zem su rovnobezne so suradnicovymi osami.

Poznamka 1: Stromy maju zanedbatelny polomer.

Poznamka 2: Klavir (ani Tomas) nevie plavat.

Poznamka pre tych, ktorym sa zda priklad lahky: Vezmite do uvahy koncertne kridlo - take koncertne kridlo ma inu polohu strun a preto ho smelo mozno v lese aj otacat.

Priklad:
Vstup:
Pocet stromov: 6
Suradnice stromov: [0,1],[3.5,3.5],[0.5,3],[2,0],[0,5],[2,1.5]
Velkost klavira: x=3,y=2

Vystup:
Klavir sa lesom preniest da.

4. The Streets of San Benatky

Benatcan~s~dlhym~a~nezrozumitelnym~menom ma problem. Mestsky urad mu nariadil rozhodnut, ktore z mostov su natolko vyznamne, ze ich absencia by dlhodobo ochromila dopravnu situaciu v meste. Most je vyznamny, ak v pripade, ze by spadol by v meste existovali aspon dve dolezite miesta, medzi ktorymi by neexistovalo ziadne spojenie. Treba si uvedomit, ze v Benatkach nemaju cesty, ale iba kanaly a mosty nad nimi (a po kanaloch prirodzene nemozno chodit, lebo by mal clovek velmi rychlo mokre topanky).

Uloha: Pomozte Benatcanovi~s~dlhym~a~nezrozumitelnym~menom a napiste program, ktory nacita pocet dolezitych miest N, pocet mostov M a dalej M dvojic cisel dolezitych miest, pricom kazda dvojica znamena, ze tieto dolezite miesta su priamo spojene mostom a potom vypise vsetky vyznamne mosty v Benatkach.

Priklad:
Vstup:
Pocet dolezitych miest: 7
Pocet mostov: 8
Mosty: (1,2),(2,3),(4,7),(1,4),(3,6),(2,4),(5,6),(3,5)

Vystup:
Vyznamne mosty su: (2,3),(4,7)

5. O Stevovej sieti

Stevo sa so svojimi kamaratmi vybral na vylet do lesa. Chodili po lese, chodili, az boli tak unaveni, ze dalej chodit nevladali. I rozhodli sa, ze si spravia obedovu prestavku.

Co mozu robit studenti Matematicko-fyzikalnej fakulty v lese, ked si spravia obedovu prestavku? To je jednoduche. Kazdy vyliezol na nejaky strom a vytiahol z batohu chlieb, slaninu, cibulu a notebook. I omrzelo ich len tak kazdy sam obedovat, do LCD displeja hladiet, nuz pospajali pocitace nahodnym sposobom do siete. Teraz sedia a nevedia, co si so sietou pocat, lebo nemaju tusenia, ako poslat jeden druhemu po sieti e-mail.

Uloha: Kazdy pocitac je spojeny s niekolkymi inymi pocitacmi, s kazdym osobitnou linkou. Kazdy pocitac ma svoje linky ocislovane od 1 po N, kde N je pocet jeho liniek. Kazdy pocitac v sieti ma jednoznacne priradene meno (retazec max. 10 pismen, ktory neobsahuje medzery - napriklad FERDO). Ak su pocitace A a B spojene linkou, moze napriklad pocitac A poslat spravu pocitacu B, sprava sa zaradi do mailboxu pocitaca B.

Predstavme si takyto sposob posielania e-mailov. Pocitac posle e-mail niektorou svojou linkou. Pocitac na druhom konci linky e-mail prevezme, zisti pre koho je, a ak nie je pre neho, posle ho niektorou svojou linkou dalej ( prerutuje ho). Aby e-maily zbytocne dlho nebludili po sieti (trebars aj na veky-vekov), kazdy pocitac musi vediet pre kazdy iny pocitac v sieti, ktorou cestou e-mail poslat, aby sa na najmensi pocet prerutovani dostal do ciela (tieto udaje su ulozene v takzvanej rutovacej tabulke).

Napiste program, ktory (pokial sa napchavaju slaninou) spustia vsetci Stevovi kamarati (Stevo je egocentricky - kamarati sa aj sam so sebou) na svojich laptopoch, pricom po jeho skonceni bude mat kazdy z pocitacov k dispozicii rutovaciu tabulku (program bezi na kazdom pocitaci nezavisle).

Pre komunikaciu medzi pocitacmi mate k dispozicii tieto procedury (pre jazyk C, pripadne iny jazyk zadefinujte procedury s podobnou strukturou; smes je to iste co string, iba s neobmedzenou dlzkou):

Send(sprava:smes; linka:integer) - pocitac posle spravu sprava po linke linka.
Receive(var sprava:smes; var linka:integer) - vyberie z mailboxu jednu spravu a vrati v premennej sprava jej obsah a v premennej linka udaj o tom, z ktorej linky sprava prisla. Ak ziadna sprava v mailboxe nie je, Receive caka az kym tam nejaka nebude.
NumberOfLinks(var n:integer) - do premnnej n ulozi pocet liniek, ktore vedu z pocitaca.
MyName(var s:string[10]) - do premennej s ulozi meno pocitaca.
Poznamka: Snazte sa, aby pocitace skoncili skor, ako studenti dojedia svoju slaninu (Stevo slaninu neje, namiesto nej je kalerab). Linky su pomale a preto sa snazte, aby ste toho neprenasali zbytocne vela.
(C) 1996, Organizers of the CSP