• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Priklady 2. kola, 17.rocnika, KSP-Z

Mili nasi riesitelia,

Ani ste sa nestihli 50 krat vyspat, odkedy ste nam naposledy nieco poslali, a uz sme vam aj odpisali. Su tu zadania druheho kola. Takze dost bolo oddychu, hor sa opat do prace. A nezabudnite dodrzat termin odoslania rieseni, ktory je tentokrat 7. februara 2000. A nezabudnite poslat znamky. A nezabudnite si umyt rano aj vecer zuby. A neza...

Nechame to na kona, ten ma vacsiu hlavu.

1. Zahada najkratsej cesty
2. Zah(r)adne mravenisko
3. Zostarnuty papagaj
4. O vcielkach
5. Zibabwejsky internet II.

---

1. Zahada najkratsej cesty

Bol teply julovy vecer a traja patraci opat sedeli v hlavnom stane. Tentoraz prebiehala vasniva debata o tom, aka je nakratsia cesta z mestskej kniznice do hlavneho stanu. Bobovi to trvalo 17 minut, Jupiter to cez podchod zvladol za 16:30 a Peter, krizom cez cinsku stvrt, to vraj zmakol za rovnu stvrthodinku. Vsetky tieto cesty vsak mali jednu vec spolocnu: ziadna netrvala rovnako dlho, a podla patracov ziadna z nich nebola najkratsia. Ked sa chylilo ku polnoci, Jupiter vyhlasil:

"Ta najkratsia cesta sa pred nami nejako skryva, a existuje vobec? Uz generacie programatorov sa sklanaju pred najkratsou cestou, pani Dijkstra, Floyd, Warshall su slavni na celom svete. Vyuzime ich sluzby, aby nam zistili, ci vlastne existuje aspon jedna najkratsia cesta."

Uloha:

Pomozte svojim kamaratom a napiste im program, ktory nacita popis mesta Rocky Beach a vypise, ci existuje najkratsia cesta z vyznamneho bodu cislo 1 (co je hlavny stan) do vyznamneho bodu cislo N (co je kniznica). Mesto sa sklada z N vyznamnych bodov ocislovanych od 1 po N, a M uliciek medzi nimi. Vas program na vstupe dostane cisla N,M a pre kazdu ulicku cisla A_i,B_i a C_i, to znamena, ze i-ta ulicka dlzky C_i>0 spaja vyznamne body A_i a B_i. Vsetky ulicky su obojsmerne.

Priklad:

Vstup

N=3, M=2
(1,2,15), (2,3,7)

Vystup

Najkratsia cesta predsa len existuje!

Vstup

N=3, M=1
(1,2,42)

Vystup

Marna vasa snaha, tu najkratsiu nikdy nenajdete!

---

2. Zah(r)adne mravenisko

"Z !" zarevala zla kralovna. Mravec Z zufalo zrychlil. Za par sekund uz bol v hlavnej komnate. "Ponizene prosim o odpustenie..." vrhol sa jej k noham. "Sedemnast tisic tristo dvadsatstyri." vydychol. Nato sa kralovna zamyslela. "A kolkoze mravcekov zije na... na... na sto dvadsiatom tretom az styristo siedmom poschodi ?" Mravec Z sa zdesene zdvihol a vydal sa opat pocitat obyvatelstvo. Z dveri ho vyprevadzal zlomyselny smiech kralovnej.

Ked tu zrazu mravec Z dostal napad. Presiel si cele mravenisko a na kazdom poschodi si zratal pocet mravcov, ktore tam ziju a zaznacil si ich do svojho pocitaca. Teraz by vsak potreboval program, ktory by vedel co najrychlejsie povedat, kolko mravcov zije v urcitej casti mraveniska.

Uloha:

Napiste program, ktory dostane na vstupe cislo N - pocet poschodi mraveniska, nasledne N cisel, ktore udavaju pocty mravcov na jednotlivych poschodiach. Potom bude nacitavat dvojice cisel X,Y (X<Y) a zakazdym vypise, kolko mravcov zije na X. az Y. poschodi. Vstup je ukonceny dvojicou (0 0).

Upozornenia:

Take mravenisko ma velmi vela poschodi, keby ich malo este viac, nemuseli by sa pocty mravcov na jednotlivych poschodiach hadam ani popratat do pamate pocitaca. Kralovna je velmi netrpezliva, preto sa snazte, aby vas program bol co najrychlejsi. Je aj poriadne skodoradostna, preto pocet otazok, ktore ubohemu Z polozi, moze byt neprijemne velky.

Priklad:

13
1 3 4 7 6 9 4 5 2 4 123 1444 32538

3 4
Na poschodiach 3-4 zije spolu 11 mravcov.

13 13
Na poschodiach 13-13 zije spolu 32538 mravcov.

1 13
Na poschodiach 1-13 zije spolu 34150 mravcov.

0 0

---

3. Zostarnuty papagaj

V jednom nemenovanom bytiku v Bratislave zije jedno slusne dievcatko menom Nanka. Ked bola este mensia, spadla jej na hlavicku kalkulacka ruskej vyroby. Dllho ju potom bolela hlavicka a od tejto chvile z duse znenavidela vsetky kalkulacky. Komplikacie nastali, az ked Nanka chodila do skoly. Ked spocitavali male cisla, stacilo jej jej desat prstov. Potom zacala pouzivat prsty na nohach. Az raz na vianoce jej priletel na balkon papagaj. A nebol to len taky obycajny papagaj... vedel pocitat. Ked mu Nanka zakricala: "plus minus desat krat dva tri osem", papagaj zacal opakovat: "dvanast, dvanast, dvanast..." A neprestal, pokial nedostal dalsi priklad. Utisil sa iba vtedy, ak ho niekto prekrical pokrikom: "Piistaa!!" A tak to islo dlhe casy a Nanka sa naucila pocitat iba v takomto divnom zapise. Lenze papagaj starne a Nanka potrebuje nahradu.

Uloha:

Na vstupe mate matematicky vyraz zapisany v prefixovej notacii. A co to vlastne znamena?

• cele cislo je vyraz v prefixovej notacii a jeho hodnota je toto cislo.
• ak v₁, v₂ su vyrazy v prefixovej notacii s hodnotami h₁,h₂, tak aj +v₁ v₂, -v₁ v₂, *v₁ v₂, /v₁ v₂, @v₁ su vyrazy v prefixovej notacii a ich hodnoty su h₁+h₂, h₁-h₂, h₁*h₂, h₁ div h₂, a ciferny sucet h₁.
• nic ine nie je vyraz v prefixovej notacii

Vasou ulohou je vypocitat hodnotu prefixoveho vyrazu na vstupe. Zvolte si vhodny format vstupu a predpokladajte, ze je korektny.

Priklad:

Vstup:

+ - 10 * 2 3 8
@ 12

Vystup:

12
3

---

4. O vcielkach

Dr. Jones, aj vdaka vasej vydatnej pomoci, stastne nasiel vychod zo zrucaniny. Dlan na pravej ruke ho palila, mal ju celu rozodratu az do krvi. Nastastie pred vychodom zo zrucaniny tiekla riecka. Sadol si k nej, ponoril ruku do vody a cakal, kym sa mu z ruky vyplavia choroboplodne zarodky. Voda bola prijemne chladna.

Potom si lahol na chrbat. Citil sa ako nikdy predtym, slniecko svietilo, bzukotali okolo neho vcielky...

V horizontalnej rovine nad jeho hlavou bzukotalo N vcielok so suradnicami [x₁,y₁],[x₂,y₂] , [x₃,y₃], ... [x_N,y_N]. Ako ich tak pozoroval, vsimol si necakane suvislosti. Vsetky vcielky sa pohybovali rovnakou konstantnou rychlostou. Navyse prva vcielka nahanala druhu, druha tretiu, atd. az (n-1)-va n-tu a konecne n-ta vcielka prvu.

Uloha:

Napiste program, ktory nacita N - pocet vcielok a pociatocne suradnice vcielok [x₁,y₁],[x₂,y₂] , [x₃,y₃], ... [x_N,y_N]a bude simulovat ich pohyb po grafickej obrazovke. Vcielky znazortnite ako male bodky.

Premiova uloha:

Zistite a hlavne zdovodnite, co by mal robit vas program pre vstup: N=4, [x₁,y₁]=[0,0], [x₂,y₂]=[0,100], [x₃,y₃]=[100,100], [x₄,y₄]=[100,0]. Ako zdovodnenie sa nebudu uznavat argumenty typu: "Moj program urobil toto."

---

5. Zibabwejsky internet II.

Zimbabwejsky kral Zimba-Zimba smutne hladel na monitor. Ma uz sice novy prehliadac, ale co ked na zimbabwejskom internete nie je vela zaujimavych stranok. Ten je totiz velmi mlady. A tak sa Zimba-Zimba rozhodol, ze sa sam nauci pisat HTML kod.

I ucil sa, i ucil, az sa nakoniec naucil. A tak cely nateseny sa rozhodol, ze napise jednu krasnu kralovsku WWW stranku. A ako inac by taka stranka mala vyzerat, ak nie s velkou hrbou obrazkov. I napisal ju a plny ocakavania spustil svoj prehliadac. Ale co to? Missing Image? Tak to hadam nie! Kto ale najde ten spravny subor? A co ak chybaju aj nejake ine obrazky? Alebo nebodaj aj ine HTML subory?

Pomozte Zimbo-Zimbovi a napiste mu program, ktory mu vypise vsetky odkazy na obrazky a HTML stranky zoradene v abecednom poradi. Format HMTL suboru ostava rovanaky ako v predoslej ulohe. To znamena ze obsahuje prikazy <HTML>, <BODY>, </BODY>, </HTML>, <CENTER>, </CENTER> a <P>. Okrem toho pribudol prikaz na vykreslenie obrazku <IMG SRC="meno">, kde meno je nazov suboru vo formate JPEG alebo GIF (s priponami JPG, JPEG alebo GIF). Taktiez odkaz na na inu stranku stranku <A HREF="meno">, kde meno je nazov suboru html (s priponou HTM alebo HTML). Za nim nasleduje text urceny na zobrazenie ako odkaz. Ten je ukonceny </A>. Vas program by mal vypisat pocet zobrazovanych obrazkov vo formate GIF a ich mena zoradene abecedne, pocet obrazkov JPEG a ich abecedny zoznam. Taktiez vypise pocet odkazov na ine stranky a abecedny zoznam tychto stranok. Dva odkazy na rovanke subory, alebo dva rovnake obrazky sa pocitaju len raz, taktiez sa vypisuju len raz. Mena suborov nerozlisuju male a velke pismena, takze INTERNET.JPEG je to iste ako iNTernEt.JpeG.

Nezabudajte, ze formatovanie vo vstupnom subore nema vplyv na samotnu HTML stranku, cize cela stranka moze byt napriklad na dvoch riadkoch - asi takto:

<HTML><BODY>Stranka<IMG SRC="auticko.gif"><CENTER>
riadok 1<P>riadok 2</CENTER></BODY></HTML>

Priklad:

Vstup:

<HTML>
<BODY>
<CENTER> Oficialna kralovska stranka Zimba-Zimbu </CENTER>
<CENTER>    <IMG SRC="KORUNA.GIF">   </CENTER>  <P>
<IMG SRC="TRON.GIF"> <P>
<A HREF="HOSTINA.HTML"> Viac o kralovaskej hostine TU </A>
<P>
<IMG SRC="TORTA.JPEG"> <IMG SRC="KOLAC.JPG">
Pridte nas vsetci pozriet, ale nezabudnite si precitat
<A HREF="PRAVIDLA.HTM"> pravidla. </A> <P>
<P> <P>
<IMG SRC="KORUNA.GIF"> Pozrite si dalsie mase stranky. Vas Zimba-Zimba.
</BODY>
</HTML>

Vystup:

Pocet GIF obrazkov: 2
KORUNA.GIF
TRONG.GIF

Pocet JPEG obrazkov: 2
KOLAC.JPEG
TORTA.JPG

Pocet odkazov na stranky: 2
HOSTINA.HTML
PRAVIDLA.HTM

---

(C) Januar 2000, webmaster@ksp.sk

---