KSP
- Home
- Novinky
- Pravidlá
- FAQ
- Kuchárka
- Liaheň
Séria
Akcie
Ostatné
Iné semináre
- Trojsten
- KMS
- FKS
- Iné súťaže

Korešpondenčný seminár z programovania

Priklady 3.kola 17.rocnika KSP-Z

Mili nasi riesitelia,

Tretie a posledne kolo je tu. Vidi sa vam, ze ich bolo nejako malo? V tom pripade vam odporucame pustit sa na buduci rok do kategorie KSP. Ale este pred tym nam do 3. aprila 2000 spolu s dakymi tymi znamkami poslite riesenia tohto kola KSP-Z.

KSPaci

Z rodinnej kroniky
Zaujimava lanovka
Zelene svahy Kiribati
Zbytocne dlhy ropovod
Zimbabwejsky internet III.

1. Z rodinnej kroniky

Bonifac je velmi nestastny. Jeho svokra Emilia ho nema rada. Stale sa s nim iba hada. Bonifac si vzal do hlavy, ze Emilia ma hadavost vrodenu a na podporu tejto idey zacal v rodinnej kronike hladat vsetkych Emiliinych pribuznych a zmienky o ich hadavosti. Ako si tak listoval v kronike, napadla ho zaujimava uloha:

Uloha

Napiste program, ktory pre danych dvoch ludi zisti, ci su v nejakom pribuzenskom vztahu a ak ano, vypise ich najblizsi pribuzensky vztah. Vstupom programu budu vypisy z kroniky tvaru:

SYN <meno syna> <meno rodica>
DCERA <meno dcery> <meno rodica>
MANZEL <meno manzela> <meno manzelky>

Prve dva zapisy hovoria, ze prvy uvedeny clovek je synom resp. dcerou druheho, treti zapis hovori, ze uvedeni dvaja ludia su manzelia.

Vas program bude dalej nacitavat dvojice mien a pre kazdu dvojicu vypise popis najblizsieho pribuzenskeho vztahu prvej osoby k druhej.

Popis vztahu je postupnost slov syn, dcera, otec, matka, manzel, manzelka v spravnych padoch. Napriklad vztah "brat" sa popise ako "otcov syn" alebo "matkin syn". Vztah je tym blizsi, cim menej slov je potrebnych na jeho popis. Niektore vztahy maju svoje skratene nazvy, napr. "matka manzelky" sa obvykle vola svokra, "syn otca" je brat. Pri vypise mozete pouzit tieto skratene nazvy, avsak toto skratenie nema vplyv na blizkost vztahu.

Poznamka

So sklonovanim vo vystupe si nelamte hlavu...

Priklad

Vstup:

SYN Bonifac Filomena
DCERA Alena Filomena
MANZEL Peter Filomena
DCERA Anicka Emilia
MANZEL Bonifac Anicka

Otazky:

Bonifac Emilia
Emilia Bonifac
Peter Emilia
Alena Bonifac

Vystup:

manzel dcery
matka manzelky
otec manzela dcery
dcera matky (alebo dcera otca)

2. Zaujimava lanovka

V pohori High Tatras je okrem Mt. Kopca aj vela inych kopcov a kopcekov. Ale zo ziadneho z nich nevedie lanovka priamo na vrchol Mt. Kopca. Zvaz lyziarov a turistov sa rozhodol tento nedostatok odstranit vybudovanim novej lanovky. A nie hocijakej, ale najdlhsej moznej. V ramci uspornych opatreni sa rozhodlo, ze lanovka sa postavi bez stlpov. Z tohto dovodu bude jej draha vyzerat ako usecka (nosne lano bude pevne napnute medzi koncovymi stanicami). Pomozte funkcionarom zvazu a napiste program, ktory im najde vhodne miesto na stavbu koncovej stanice lanovky.

Uloha

Hreben pohoria dlzky N kilometrov vyzera pri pohlade zvrchu ako rovna usecka. Pri pohlade zboku vidime N+1 vyznacnych bodov (na kazdom kilometri jeden), pricom kazda dvojica susednych vyznacnych bodov je spojena useckou. Tieto usecky dokopy tvoria hreben. Pre kazdy vyznacny bod i (0<=i<=N) je samozrejme znama jeho nadmorska vyska A_i v kilomeroch (realne cislo).

Vrchol Mt. Kopca lezi na kilometri 0 a tvori jednu koncovu stanicu. Vasou ulohou je napisat program, ktory zisti, na ktorom vyznacnom mieste na hrebeni treba postavit druhu koncovu stanicu tak, aby draha lanovky viedla vzdy nad povrchom a jej dlzka bola pritom najvacsia mozna.

Priklad

Vstup: N=5
A₀=4, A₁=0, A₂=0, A₃=2, A₄=0, A₅=0

Vystup:

Nastupnu stanicu treba umiestnit na 2. kilometer, potom bude lanovka dlha 4,47 km.

Obrazok lanovky

3. Zelene svahy Kiribati

Kiribatske deticky maju prazdniny, a tak sa najlepsi priatelia Mwango a Itab-irik rozhodli, ze sa pojdu lyzovat. Pekna myslienka, az na to, ze na Kiribati byva pomerne teplo a nie je vobec jednoduche najst nejaky zasnezeny kopec. "Podme na ostrov, na ktorom je najviac kopcov. Tak mame najvacsiu nadej, ze si tejto zimy zalyzujeme!" povedal Mwango. A tak si sadli nad mapu Kiribati a zacali pocitat kopce na jednotlivych ostrovoch. Po chvili to vsak vzdali a vyhlasili, ze to je robota pre kona. Alebo pre pocitac.

Uloha

Na vstupe su dve cisla M, N - rozmery mapy Kiribati a vyskova mapa Kiribati. Vode zodpoveda vyska 0, susi vyska vacsia ako 0. Okraj mapy tvori voda. Dve policka su susedne, ak sa dotykaju stranou. Dve policka suse patria k tomu istemu ostrovu prave vtedy, ked sa da z jedneho na druhy prejst po susi tak, ze vzdy prejdeme na susedne policko. Policko suse je kopec prave vtedy, ked je vyssi od vsetkych styroch svojich susedov. Napiste program, ktory vypise suradnice x_p,y_p niektoreho policka ostrova, na ktorom lezi najviac kopcov.

Priklad

Vstup:

M=6, N=8
0 0 0 0 0 0 0 0
0 2 4 1 0 0 6 0
0 3 4 1 0 7 2 0
0 0 1 0 0 0 4 0
0 0 0 0 9 0 0 0
0 0 0 0 0 0 0 0

Vstup:(2,7)

Poznamka: (Na tomto ostrove su 3 kopce. Na ostrove obsahujucom (5,5) je jeden kopec a na ostrove obsahujucom (2,2) nie je ziaden.)

4. Zbytocne dlhy ropovod

Novy nalez ropy na Ukrajine podnietil slovensku vladu co najrychlejsie vybudovat tranzitny ropovod na nasom uzemi. Stavat sa zacalo narychlo, bez poriadneho projektu, takze planovanie vacsinou vyzeralo tak, ze za stavbyveducim prichadzali striedavo zastupca SPP a splnomocnenec vlady pre energetiku a prikazovali, ktorym smerom ma viest najblizsi usek.

Na zjednodusenej mape Slovenska (stvorec NxN kilometrov) ropa priteka na policko v pravom hornom rohu mapy. Vyustenie ropovodu ma byt na policku v lavom dolnom rohu. Kazdy usek zabera jedno policko mapy. Sklada sa z dvoch rur, z toho jedna sa vzdy napaja na uz postavenu cast ropovodu a druha je kvoli moznemu buducemu rozsireniu (tzv. buduca rura). Useky su jedneho z troch druhov:

      \              /              |
    \   \          /   /          --+--     (5x3 znakov obrazovky)
      \              /              |
 sever-vychod   sever-zapad    sever-juh
   juh-zapad     juh-vychod   zapad-vychod

Prvy druh useku sa sklada z rury spajajucej stred severnej a vychodnej strany policka a rury spajajucej stredy zapadnej a juznej strany. Druhy druh vznikne otocenim prveho o 90 stupnov. Posledny druh sa sklada z dvoch kriziacich sa rur spajajucich severnu s juznou a vychodnu so zapadnou stranou policka.

Moze sa stat, ze rura novopostaveneho useku, ktora je jednym koncom pripojena k hotovej casti ropovodu sa svojim druhym koncom nadpoji na nejaky usek buducej rury. V takomto pripade sa samozrejme tento usek a vsetky nadvazujuce useky pripajaju k ropovodu. Nasledujuci usek ropovodu sa potom stavia na policku nadvazujucom na koniec pripojenej casti.

Uloha

Urobte program zjednodusujuci planovanie stavby ropovodu. V nultom tahu sa da vybrat, ci ropa na uzemie Slovenska vteka na zapad, alebo juh. V kazdom dalsom tahu sa vybera dalsie smerovanie ropovodu - pismenom 's','j','v','z' oznacujucim svetovu stranu na ktoru ma smerovat rura noveho useku pripojena na doteraz postavenu cast.

Pre N=3, hra po siestom tahu:                 Boli stlacene klavesy:
    .................                           0.tah: 'z'
    .       /  XXXXX.                           1.tah: 'j'
    .     /   /XXXXX.                           2.tah: 'j'
    .       /  XXXXX.                           3.tah: 'v'
    .  /    |    \  .                           4.tah: 's'
    ./   /--+--\   \.                           5.tah: 'z'
    .  /    |    \  .                           6.tah: 'j'
    .YYYYY  \    /  .
    .YYYYY\   \/   /.
    .YYYYY  \    /  .
    .................

Poznamka

Mozete pouzit aj krajsie znaky pre potrubia, ale pouzivajte iba textovy rezim zobrazovania.

5. Zimbabwejsky internet III.

Zimbabwejsky internet nebol este nikdy na kralovom hrade taky popularny, ako teraz, ked sa sam velky Zimba-Zimba naucil HTML stranky vytvarat. Vytvaral, vytvaral, az jedneho pekneho zimneho dna prisiel na to, ze vytvorenymi strankami zaplnil cely disk a ze sa mu tam uz ziadna nova stranka nepomesti. Rozhodol sa preto vymazat vsetky nepotrebne stranky, teda take, na ktore sa neda dostat prechadzanim po odkazoch z hlavnej kralovskej stranky. Na to najprv potrebuje zistit, na ktore stranky sa to vlastne dostat da. Napiste program, ktory mu s tym pomoze, inak bude musiet vymazat cely disk a zacat tvorit vsetky stranky od zaciatku.

Uloha

Na disku je ulozene mnozstvo html suborov (s priponou .HTM) obsahujucich stranky vytvorene Zimbom. Hlavna kralovska stranka je ulozena v subore INDEX.HTM. Vsetky stranky maju rovnaky tvar ako v predchadzajucich ulohach, teda mozu obsahovat prikazy <HTML>, </HTML>, <BODY>, </BODY>, <CENTER>, </CENTER>, <P>, <IMG SRC="...">, <A HREF="..."> a </A>. Prikaz <A HREF="MENO.HTM"> na html stranke znamena odkaz na stranku ulozenu v subore s menom MENO.HTM. Odkazovana stranka moze samozrejme obsahovat dalsie odkazy. Hovorime, ze zo stranky A sa da dostat na stranku B, ak existuje taka postupnost stranok A=s₁,s₂,...,s_n=B, ze stranka s_i obsahuje odkaz na stranku s_i+1 pre 1<=i<n. Ulohou vasho programu je vypisat mena suborov so vsetkymi strankami, na ktore sa da dostat z hlavnej stranky v subore INDEX.HTM. Na poradi vypisovania nezalezi, ale kazdu stranku by ste mali vypisat iba raz.

Priklad

Subor INDEX.HTM:

<HTML><BODY>
<CENTER>Kralovska stranka</center><p>
<A HREF="MENO.HTM">Ako sa volam</a><p>
<A HREF="SUSEDIA.HTM">Susedne krajiny</A>
</BODY></HTML>

Subor MENO.HTM:

<HTML><BODY>
Ja som Zimba-Zimba <IMG SRC="ZIMBA.JPG"><p>
Chodim rad do <A HREF="KINO.HTM">kina</A>.
</BODY></HTML>

Subor KINO.HTM:

<HTML><BODY>
Toto je nase kino.
</BODY></HTML>

Subor SUSEDIA.HTM:

<HTML><BODY>
Tato stranka sa prave pripravuje.
Mozte sa vratit <A HREF="INDEX.HTM">naspat</A>.
</BODY></HTML>

Vystup:

INDEX.HTML
MENO.HTM
KINO.HTM
SUSEDIA.HTM

Podporte nás

Účet

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

kontakt