KSP.sk

Korešpondenčný seminár z programovania

Priklady 2. kola

Mili nasi riesitelia,

v prvom rade vam chceme vsetkym popriat bohatu nadielku pod vianocnym stromcekom, vela snehu a peknu lyzovacku. Ak si pri tom vsetkom este najdete case aj na KSP, potom sa na vase riesenia druhej serie KSP kategorie Z tesime do 9. februara 1998. Nezabudnite na znamky a (ti, co ich este neposlali) na navratky. Ak nahodou budete travit prazdniny na nejakom peknom mieste a spomeniete si na nas, mozete nam odtial poslat pohladnicu. Vopred dakujeme.

Pravidelne si cistite nos!

KSPaci

  1. Zavisove slimaky
  2. Zeofinina nocna mora
  3. Zanzibarsky slon
  4. Zvedavy Jonatan
  5. Zaclony carodejnice Kirky

1. Zavisove slimaky

Zavis dostal dalsi napad, ako zbohatnut: zalozil si farmu na slimaky. Slimaky sa prechadzali po jeho zahradke a utesene rastli. Zavis si vsimol, ze kazdy mesiac slimakovi dorastie jeden zavit ulity. Aby si ziskal zakaznikov, rozhodol sa, ze vyda ponukovy katalog s obrazkami rozne starych slimakov. Kedze nema fotoaparat, chcel by tlacit obrazky na pocitaci.

Uloha: Napiste program, ktory nacita vek slimaka (v mesiacoch) a smer natocenia (vlavo alebo vpravo) a vytlaci na tlaciarni prislusneho slimaka. Presny tvar slimaka iste lahko vypozorujete z prikladu.

Poznamka: Tlaciaren vie vypisovat znaky iba postupne zlava doprava a po riadkoch zhora nadol. Ak pracujete v Turbo Pascale, mozete na vystup na tlaciaren pouzit unit PRINTER (pri pouziti tohto unitu vypisujete na tlaciaren prikazmi write(lst,...), resp. writeln(lst,...)).

Priklad:
vek: 1 mesiac, smer: vlavo 

H *
H**
vek: 2 mesiace, smer: vpravo 
****
*  *   
* **   
*     H
******H
vek: 3 mesiace, smer: vlavo 
   ********
   *      *
   * **** *
   * *  * *
   * ** * *
   *    * *
   ****** *
H         *
H**********

2. Zeofinina nocna mora

Kym Zeofina nakreslila vsetky galapagske stromy, na ktore si spomenula, padol sumrak. A Zeofine nebolo viac treba, nevahala a zaspala ako nemluvna. Nebol to vsak spanok, pri ktorom si clovek (alebo skor korytnacka) oddychne. Iba sa prehadzovala z boka na bok. Zase ta nocna mora. Mava ju od cias, ked ju v Kahire nutili preliezat bludiska. Chceli, aby presla kazdou chodbickou bludiska, ale ziadnou nesmela ist dvakrat. V jej sne najprv cele bludisko pozostavalo iba z jednej chodbicky. Uz-uz sa chystala, ze nou prejde, ked sa zrazu chodbicka po oboch stranach vyliacila a okrem povodnej tu boli aj dve bocne chodbicky. Vchod do nich a vychod z nich delili povodnu chodbicku na tretiny. Kazda z tychto novych chodbiciek sa skladala z troch rovnako dlhych usekov (s dlzkou jednej tretiny povodnej chodbicky), ktore zvierali pravy uhol. Kym si vsak Zeofina rozmyslela, ako pojde teraz, opat sa kazdy priamy usek (medzi dvoma krizovatkami, zakrutami, vchodom, vychodom) po oboch stranach vyliacil a takto sa to opakovalo, kym sa Zeofina prepotena nezobudila. Zeofine by sa velmi ulavilo, ak by vedela, ako treba bludisko z jej nocnej mory vlastne prejst.

Uloha: Bludisko stupna 0 ma iba jednu priamu chodbu (mozno ho teda nakreslit ako usecku). Bludisko stupna n+1 vznikne z bludiska stupna n tak, ze cez prostrednu tretinu kazdeho priameho useku dlzky l prelozime obdlznik so stranami 2l/3 (tie delia usek na tretiny a zaroven ich usek deli na polovice) a l/3. Dlzka najkratsieho priameho useku chodby je d.

Napiste program, ktory nacita cisla n a d a poradi korytnacke Zeofine, ako ma prejst bludiskom stupna n tak, aby presla kazdou chodbickou prave raz. Ako vystup vypiste seriu pokynov pre korytnacku Zeofinu. Korytnacka vie reagovat na tieto pokyny: Dopredu a - posunie sa v smere svojho natocenia o dlzku a, Vlavo u - otoci sa o u stupnov vlavo, Vpravo u - otoci sa o u stupnov vpravo.

Priklad:

Obrazok labyrintov pre n=1 a n=2

3. Zanzibarsky slon

V dalekom Zanzibare sa genetickym inzinierom podaril maly zazrak, vypestovali specialny druh slona, ktory ma oproti klasickemu slonovi velku zvlastnost, nielen jeho kly, ale vsetky jeho kosti su zo vzacnej slonoviny. Kedze Zanzibar je chudobny stat, rad by na svojom unikatnom slonovi zarobil. Rada starsich sa teda rozhodla, ze preda niektore kosti svojho slona a takto ziskane peniaze venuje na rozvoj kultury. Problem je vsak v tom, ze nechcu svojmu slonovi ublizit.

Zanzibarsky vedci podrobne preskumali slona a prisli na to, ze ich slon ma v tele takzvane vyznamne uzly a jeho kosti spajaju vzdy dva z tychto uzlov. Dalej zistili, ze ked slonovi odoberu niektore kosti, slon ostane zdravy, ak bude jeho kostra nadalej suvisla, co znamena, ze kazde dva vyznamne uzly budu nejakym poctom kosti (aj cez ine uzly) navzajom prepojene. Teraz uz ostava zistit ktore kosti treba odobrat, aby Zanzibar svojmu slonovi neublizil a pritom kosti, ktore po operacii slonovi ostanu mali co najmensiu cenu.

Uloha: Napiste program, ktory nacita popis kostry slona a vypise popis kostry po operacii, ktora slonovi neublizi (kostra ostane suvisla) a zaroven kosti, ktore v slonovi ostanu, budu mat najmensiu moznu celkovu cenu. Popis kostry (aj pri vstupe aj pri vystupe) zacina riadkom obsahujucim pocet vyznamnych uzlov slona N a pocet kosti v kostre M. Potom nasleduje M riadkov, pricom kazdy z nich obsahuje informaciu o jednej slonej kosti a to tri cisla A,B a C, ktore hovoria, ze kost spaja vyznamne uzly A a B a jej cena na ciernom trhu je C.

Priklad:
Vstup:

5 6
1 3 5
5 1 3
2 4 9
4 3 4
1 4 1
4 5 4
Vystup:
5 4 1 5 3 2 4 9 4 3 4 1 4 1

Obrazok kostry slona

4. Zvedavy Jonatan

Ked sa Jonatan rano zobudil, ledva-ledva sa zmohol na cestu do kuchyne. Unavene sledoval mamu, ako mu pripravuje ranajky. Najskor polozila na stol chlieb, potom nakrajala syr, uhorky, papriku a ine dobroty na tenucke platky a zacala to ukladat na Jonatanov krajec. Potom Jonatan zobral vidlicku a bez rozmyslu na nu napichol chlieb. Ale beda! Na vidlicke zostalo len trochu zeleniny a zo dva platky syra, chlieb aj s ostatnou oblohou zostal na stole. Taka neprijemnost hned zrana Jonatana do noveho dna velmi nepovzbudila.

Uloha: Predpokladajme, ze chlieb je obdlznik s rozmerom AxB (kde A a B su cele kladne cisla mensie ako 100) a vsetky druhy oblohy na chlebe su tiez obdlznikove s rovnakou hrubkou 1. Navyse jednotlive kusky oblohy su poukladane tak, ze ich strany su rovnobezne so stranami obdlznika tvoriaceho chlieb. Ziadna cast oblohy neprecnieva cez krajec. Lavy dolny roh krajca ma suradnice [0,0]. Vidlicka ma zuby dlzky k a teda chlieb nou mozno napichnut iba na tych miestach, kde je na chlebe menej ako k platkov oblohy.

Napiste program, ktory nacita rozmery a suradnice umiestnenia kazdeho kusku oblohy a dlzku zubov vidlicky a vypise, ci existuje na chlebe miesto, kde sa vidlicka nedostane az po chlieb (t.j. ci existuje bod, ktory lezi vo vnutri aspon k obdlznikov urcujucich jednotlive platky oblohy).

Priklad:
Vstup:
A = 7, B = 8, K = 3

Rozmery     Lavy dolny roh
------------------------------------------
4x4         [1,1]
2x2         [4,6]
3x1         [3,3]
2x5         [2,2]

Vystup:
Na chlebe existuje miesto, kde sa vidlicka zabodne iba do oblohy!

5. Zaclony carodejnice Kirky

Carodejnica Kirka si kupila nove zaclony. Nie ze by sa jej nepacili pavucinky jej domacich milacikov, jednoducho sa jej po dlhych rokoch zaziadalo cosi zmenit. Nove zaclony musia byt samozrejme vzorne rovnomerne zavesene, aby vynikol ich vzor. Okrem toho vzdialenost dvoch susednych stipcov moze byt najviac d, lebo inak by zaclony nepekne ovisali.

Kirka si na vesanie vymyslela efektny sposob. Vyuziva pri tom svoj certovsky dobry odhad, pomocou ktoreho vie presne urcit stred medzi dvoma bodmi, v ktorych je zaclona upevnena. Najprv upevni zaclonu na oboch koncoch. Pomocou svojho certovsky dobreho odhadu upevni zaclonu presne v jej strede. Potom postupuje tak, ze si vzdy vyberie nejaky usek medzi dvoma stipcami, ktory je este dlhsi ako d a presne v strede tohto useku pripevni zaclonu dalsim stipcom. Tak postupuje, kym vsetky useky nemaju dlzku nanajvys d. Je zrejme, ze nakoniec bude zaclona zafixovana v pravidelnych intervaloch. Problem je v tom, ze Kirka uz nie je ziadna storocna mladica a jej stare klby si ziadaju co najmenej pohybu. Preto chce jednotlive useky rozdelovat v takom poradi, aby jej starucka ruka presla pri vesani zaclony najkratsiu moznu vzdialenost.

Uloha: Napiste program, ktory nacita dlzku zaclony l a maximalnu vzdialenost susednych stipcov d a vypise, v akom poradi treba vesat jednotlive stipce, aby sa Kirka co najmenej narobila. Jednotlive stipce vo vystupe zadavajte ich vzdialenostou od laveho okraja zaclony.

Dolezitou sucastou riesenia je tiez dokaz, ze postupnosti, ktore vypisuje vas program, su skutocne tie najlepsie.

Priklad:
Vstup:
l=8, d=1
Vystup:
Kirkina ruka musi prejst vzdialenost 23.
Poradie stipcov:
0,8,4,2,1,3,6,7,5
(existuju aj ine rovnako vhodne poradia)

1997, Organizers of the CSP
Podporte nás

Účet

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

Redirecting