Zadania Krajského kola súťaže ZENIT v programovaní
v školskom roku 2006/2007 pre kategórie A, B.
Všeobecné pokyny.
Čas
na riešenie úloh je 4 hodiny 30 minút.
Ú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). Ak robíte v
jazyku C/C++, vytvorte aj EXE súbor. Môžete použiť štandardné knižnice
uvedených dialektov. Nezabudnite do
komentárov na začiatku programu uviesť svoje meno, triedu a školu.
Váš program bude čítať vstupné
údaje zo súboru VSTUP.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. Pri určovaní
postupujúcich do ďalšieho kola môžu zohrať rozhodujúcu úlohu prémiové body za
kratší čas behu vášho programu pri ostrých testoch.
Zadanie úlohy: GANDALF – čarodejnícky učeň.
Bielovlasý Gandalf spomína. V
dávnych dobách, keď ešte ľudia vedeli, čo je to logaritmické pravítko
a milimetrový papier, to mal čarodejnický učeň veľmi ťažké. Skôr ako sa
stal Gandalf takým učňom na ROKFORDskej škole, musel vyriešiť 5
gigantických úloh a to bez PC. Teraz
má každý z vás možnosť využiť PC, naprogramovať ich riešenie a tak
presunúť "great part of the job"
(veľkú časť roboty) na PC. Tieto úlohy ako si Gandalf doteraz pamätá, sú to a)
až e).
Napíšte
program (a uložte ho pod svojím menom
v komentári na úvod uveďte svoje meno, triedu a školu), ktorý
vyrieši tieto problémy:
0)(12
bodov)
Od pozície (2,2) vypíše text: 'Gandalfove
ulohy: K=?'. Číslo K prečítajte
zo vstupu.
a)(10+10
bodov)
Nájdite najväčšie a najmenšie K-miestne
číslo s rôznymi ciframi, ktoré pri delení 6 dáva zvyšok 1. Výsledok
vypíšte od pozície (2,4-5).
b)(11+13
bodov)
Pre dané K vypočítajte, koľko
je všetkých K-miestnych čísiel,
ktoré majú všetky cifry rôzne a
potom počet tých, ktoré majú práve jednu
dvojicu rovnakých cifier. Výsledok vypíšte od pozície (2,6-7).
c)(8+12
bodov) Nájdite
najmenšie číslo X, ktoré pri
násobení číslom Z (zloženým z K sedmičiek) dáva samé dvojky (napr. 77
x 2886 = 222222). Počet týchto dvojok a číslo X vypíšte od pozície (2,8-9). Ak má X viac ako 12 cifier, vypíšte iba prvých 12.
d)(10+15
bodov)
Koľko K-miestnych čísiel má takú
vlastnosť, že každých ich prvých T
cifier je deliteľných T. Na pozíciu
(2,10) vypíšte najväčšie z nich a na pozíciu (2,11) ich počet.
e)(10+5
bodov)
Prečítajte ďalších 6 celých čísiel.
Vynásobte ich medzi sebou, každé s každým (15 dvojíc). Na (2,12) vypíšte, koľko
navzájom rôznych súčinov ste
dostali. Na (2,13) vypíšte najväčší z nich.
ROKFORD - Gandalfova čarodejnícka škola.
Jej plán si Gandalf už nevie celkom
presne v pamäti vybaviť. Pôdorys mal tvar obdĺžnika. Na jeho obvode je iba jeden vchod. Zachoval sa ešte Bilbov nákres (vysvetlivky pri popise
vstupu).
f)(8+9
bodov) Prečítajte zo súboru tento Bilbov plán a vypíšte od pozície (25,1). Škola mala iba jeden
vchod, nájdite jeho súradnice a vypíšte na pozíciu (1,15).
g)(5+9+9+8+8+7
bodov) Gandalfa ešte dnes stále prenasleduje po nociach zvuk vŕzgajúcich dverí. Musel
každý pondelok namazať ich pánty. Počet dverí vypíšte na pozíciu (15,15). Na
pozíciu (1,16) vypíšte, koľko je v škole miestností. Na pozíciu (1,17) vypíšte
plochu najväčšej z nich ( je iba 1) a na pozíciu (15,17) vypíšte, koľko má
dverí. Ďalej na pozíciu (15,16) plochu tajnej komnaty ( nemá dvere, je iba
jedna v celej budove). Na pozíciu (2,19) vypíšte plochu všetkých
miestností dohromady.
h)(8+8+44
bodov) Bilbo sa chcel dostať sám ku kameňu
mudrcov, ale prepadol a zranil ho troll. Krvácajúci Bilbo sa plazil od vchodu až do bodu (x;y) a všetky dvere po ceste nechal otvorené. Na pozíciu
(2,20) vypíšte dĺžku Bilbovej cesty
a aj počet dverí, ktoré nechal otvorené. Na pozíciu (2,22) koniec cesty
(x;y). Stopy po Bilbovi musel Balin vyupratovať a dvere pozatvárať.
Pre smrteľníka je to robota veľmi nebezpečná. Použil teda Balin robota menom ROBO,
ktorý pozná príkazy: D – dopredu, L - otoč sa doľava, P - otoč sa doprava. Na pozíciu (2,23)
vypíšte program pre tohto ROBOa tak,
aby prešiel cestu, ktorú preplazil Bilbo.
i)(55
bodov)
Tam, kde je na pláne znak '$' je schovaný legendárny Kameň mudrcov. Gandalf tam chce poslať ROBOa,
ale, pretože ide o kameň mudrcov, jeho program musí byť najkratší zo všetkých
možných. Na (2,24) vypíšte tento program (ak ich je viac, tak ľubovoľný
z nich ). Ak sa vám podarí dlhšie riešenie dostanete za každý povel
naviac o 5 bodov menej.
Ukážka toho, čo by mal obsahovať Váš program:
Plan :
array[1..25] of string[60];
Begin
clrscr;
assign(input,'VSTUP.in');
reset(input);
readln(K,c[1],c[2],c[3],c[4],c[5],c[6],r,s);
for i := 1 to R
do readln(Plan[i]);
...
2 1 2 4 8 5 -16 1
< K < 11 c1,c2,..,c6 - typ
integer - 2byte
7 7 3
< R < 22 5 < S < 56
#######
d*.***# Plán
školy - obdĺžnik, po obvode steny, 1 vchod
#*#*#*# # ..stena
#***#*# . ..prázdny štvorček
###.#*# D ..zatvorené dvere
#.#$.*# * ..krvavá stopa po Bilbovi
####### d ..otvorené dvere cez ktoré sa preplazil
Bilbo
$ ..poklad - Kameň Mudrcov
~~~~~~~~~~~~~~~~~~~~~~~~#######~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Gandalfove~ulohy:~K=2~~d*.***#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~#*#*#*#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~13~mod~6~=~1~~~~~~~~~~~#***#*#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~97~mod~6~=~1~~~~~~~~~~~###.#*#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Rozne:~81~~~~~~~~~~~~~~#.#$.*#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~2~rovnake:~9~~~~~~~~~~~#######~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~2~-~6~krat~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~X:~2886~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Pocet:~41~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~98~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Sucinov:~14~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Max:~40~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Vchod:~1;2~~~~Dvere:~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Komnaty:~2~~~~Tajna:~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Max.:~17~~~~~~1~dvere~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Plocha~skoly:~18~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Bilbo:~14~cez:~1~dvere~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Na:~(6;6)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Cesta~Bilba:~DPDDLDDLDDPDDPDDDD~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~ROBOT:~DDDPDDDD~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
( výpis je iba na šírku 60, medzery sú
vypisované ako '~' )