Zadania školského
kola súťaže ZENIT v programovaní
v školskom roku 2004/2005 pre kategórie A, B
Všeobecné
pokyny
Úlohu riešte v jazyku Pascal (dialekt Turbo Pascal v.7.0 alebo kompatibilný) alebo C (dialekt Turbo C++ v.3.0 alebo kompatibilný). Zdrojový text vášho
riešenia uložte do súboru priezvisko.PAS resp. priezvisko.CPP (celé riešenie musí byť uložené v tomto
súbore). Môžete použiť štandardné knižnice uvedených dialektov.
Váš program bude čítať vstupné údaje zo súboru
TEST.IN a vypisovať riešenia na obrazovku počítača vo formáte presne
stanovenom zadaním úlohy. Môžete predpokladať, že vstupné údaje zodpovedajú
popisu v zadaní. Riešenie píšte bielou farbou na obrazovku
v štandardnom textovom móde, pred začatím vlastnej činnosti programu
nezabudnite zmazať obrazovku, nevypisujte na obrazovku žiadne iné informácie
okrem tých, ktoré sú požadované zadaním.
Nemusíte riešiť všetky podúlohy
zadania, každá časť je bodovaná samostatne. Programy, ktoré nemožno skompilovať
alebo spustiť nebudú hodnotené. Pri nejasnostiach sa riaďte ukážkou výstupu
alebo testovacím programom. Ostré bodovanie prebehne na celkom iných vstupných
súboroch.
Zadanie úlohy: Labyrint kráľa Minoa.
Napíšte program, ktorý vyrieši tieto problémy:
0) (10 bodov) Na pozíciu
(2,2) napíšte text: 'Labyrint' (bez apostrofov).
a) (2 body) Daidalos so synom Ikarom
postavili kráľovi Minoovi palác - Labyrint. Ako
odmenu dostali celoživotný pobyt na ostrove Kréta. Slávny staviteľ sa chcel
vrátiť na pevninu, preto zostrojil zvláštny GumiDžúsový
lietajúci stroj. Mechanizmus stroja bol upravený tak, že výška letu sa náhle
menila s každým preleteným kilometrom podľa pravidla:
NovaVyska = 3*StaraVyska + 1, keď StaraVyska je nepárne číslo,
StaraVyska / 2, keď StaraVyska je
párne číslo.
Stroj mohol odštartovať iba na schodišti pod vrcholom najvyššej hory (teraz
by sme povedali štartovacej rampy). Podľa čísla schodu sa automaticky nastavila
štartovacia výška. Keď stroj dosiahol výšku 1 - bol na hladine mora a rýchlo sa
potopil. Prečítajte zo súboru číslo schodu S, z ktorého odštartoval Ikarus. Vypočítajte v akej vzdialenosti od ostrova
dopadol do mora. Výsledok napíšte na pozíciu (2,4).
b) (3 body) Aké výšky ostali
zaznamenané v čiernej skrinke, ktorú vylovil Neptún, boh mora, vypíš od pozície (2,5). V čiernej
skrinke sú zaznamenané všetky výšky, ktoré stroj dosiahol podľa výpočtu
v časti a).
c) (3+2 body) Zistite, na
ktorom kilometri je zaznamenaná najvyššia výška. Najvyššiu výšku vypíšte od
pozície (2,6) a kilometer, na ktorom bola dosiahnutá od pozície (20,6).
d) (7 bodov) Otec Daidalos pochodil lepšie ako Ikarus.
Prečítajte zo súboru čísla SD a Dlz, kde SD je číslo najvyššieho schodu na,
ktorý sa bol Daidalos schopný vyštverať,
Dlz je vzdialenosť z Kréty do Helady.
Od pozície (2,8) vypíšte, z ktorých schodov mohol Daidalos
odštartovať, aby sa dostal na pevninu. Schody vypíšte od najnižšieho po
najvyšší.
e) (6 bodov) Zeus Hromovládny
sa nerád pozerá na lietajúcich smrteľníkov a zakaždým, keď prekročia výškový
limit, mocne zahrmí. Vieme, že Daidalos sa bleskov
bál a preto si zo schodov, z ktorých môže odštartovať vybral ten, s najmenším
počtom bleskov.
Prečítajte LIMIT a od (2,9) vypíšte číslo schodu s najmenším počtom bleskov. Ak
je takých viac, vypíšte najnižší z nich.
f) (5bodov) Od (2,10)
vypíšte, z ktorého schodu (menšieho ako SD) môže Daidalos
zaletieť na svojom GumiTryskaci najďalej.
Text k nasledujúcim úlohám
Veľa rokov krvilačný Minotaurus žil v Labyrinte
kráľa Minoa a každý rok dostal krásnu devu. Teraz je na
rade Ariadna, dcéra kráľa Minoa.
Tézeus sa hotuje Minotaura
zabiť, aby tak uchránil nešťastnú Ariadnu.
Prečítajte zo vstupného súboru plán Labyrintu. Prečítajte najskôr N, M
(počet riadkov, počet znakov v riadku) a potom plán labyrintu. V pláne
labyrintu môžu byť tieto znaky:
'.' nezastavané miesto
'M','T' Minotaurus,
Tézeus
'X' kamenná stena
g) (5+5bodov) Úrad
špeciálneho prokurátora chce vedieť, kde sa nachádzajú Minotaurus
a Tézeus. Ich pozíciu vypíšte od (2,12) a (2,13);
h) (3+3+3 body) Pre Krétsky
bytový úrad sú dôležité niektoré údaje o priestoroch Labyrintu. Spočítajte
štvorčeky, ktoré nezaberajú kamenné steny. Vyrátajte aj spotrebu kamenných
kvádrov (kamenná stena má všade výšku 5 kvádrov) a zistite počet vchodov (vchod
je štvorček '.' na obvode).
Od (2, 15) vypíš plochu, (2, 16) počet kameňov a (2,17) počet.
i) (10 bodov) Od (2,19) vypíš
na najmenej koľko krokov môže Tézeus nájsť Minotaura. Pri každom kroku prejde Tézeus
na susedný štvorček. Susedné štvorčeky majú spoločnú jednu stranu.
j) (11 bodov) Od (2,20) vypíš
koľko najmenej krokov treba Tézeovi urobiť od mŕtvoly
Minotaura k najbližšiemu vchodu .
k) (9+10 bodov) Keby tak
vedel Minotaurus čo ho čaká. Rozobral by niektorú zo
stien, znovu za sebou zamuroval a Tézeus by ho
nenašiel. Koľko je v Labyrinte takýchto tajných priestorov, kde by mohol
uniknúť. Zistite ich počet a vypíšte od (2,22). Zistite súradnice najbližšieho
kvádra (podľa počtu krokov), cez ktorý by sa Minotaurus
dostal do bezpečia tajnej komôrky. Jeho
súradnice vypíšte od (2,23) (ak ich je viac zoberte ten naj-juho
a naj-západnejší).
Vstupny subor:
TEST.IN
5 2 < S, SD, Dlz < 200
55 66 200 LIMIT < 20 000
5 15 2 < N, M < 44
XXXXX.XXXXX.XXX
X..X....X...X.X Zaručene sa nájde
XTXXX.X.X.X.XXX – aspoň jeden vchod
X.....X...XM..X – aspoň jedna tajná miestnosť
XXXXXXXXXXXXX.X – aspoň jedna cesta od ’T’ ku ’M’
obrazovka testu: 1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Labyrint~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Ikaros~dopadol~na:~6Km~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Vysky:~5~16~8~4~2~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Max.Vyska:~16~~~~~na:~2Km~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Daidalos:~~27~31~41~47~54~55~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Zo~schodu:~27~Pocet~bleskov:~10~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Zo~schodu:~54~dolet:~113Km~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Minotaurus:~(12;4)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Tezeus:~~~~~(2;3)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Plocha:~29~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Kamen:~230~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Vchody:~3~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~k~Minotaurovi:~19~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Na~slobodu:~3~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Tajne~miestnosti:~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Tajne~dvere:~(14;3)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Poznámky
Výpis je iba na šírku 60, medzery sú vypisované ako '~' Ak si chcete svoj
program otestovať, použite UNIT uTezeus (tento unit Vám pripraví aj vstupný súbor). Po skončení sa
výsledky pripíšu do súboru 'v.pas'.
Ukážka toho, čo by mal obsahovať Váš program:
uses uTezeus,
crt;
var i, S, SD, Dlz, Limit : longint;
A : array[1..22] od string;
begin
clrscr;
assign( input, 'test.in' ); reset( input );
( citanie vstupnych dat )
read( S, SD, Dlz, Limit );
readln( N, M );
for i := 1 to N do readln( A[i]
);
... vypocty
a vypisy vysledkov
end.
Iny vstupny subor:
TEST.IN
7
101 88 1500
22 28
X.XXXXXXXXXXXXXXXXXXXXXXXXXX
X..........................X
X...XXXXXXXXXXXXXXXXXXX....X
X..................X..X....X
X............XXXX..XXXX....X
X.XXXXXXXXXXXXXX...X..X....X
X............X.XXXXXXXX....X
X............X.....X..X.....
XXXXXXXXXXXX.X....XXXXX....X
X............XXXX.X..X.....X
X.XXXXXXXXXXXX....X..XXX...X
X............X....X..X.X...X
X............X.XXXXXXXXXXX.X
XXXXXXXXXXX..X.............X
.............X.............X
X............X..XXXXXXXXX..X
X...XXXXXXXXXX..X.......X..X
X............X..X.......X..X
.............X..X.......X..X
X........T...X..X....M..X..X
X............X..X..........X
XXXXXXX.XXXXXXXXXXXXXXXXXXXX