Zenit 2006 krajske kolo...

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:

uses uTest, crt;
var K, R, S, i,j : longint;
    C : array[1..6] of integer;
    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);

  gotoxy(2,2);  write( 'Gan... : K=?');
  for i := 1 to R do readln(Plan[i]);

  ...

end.
 

Vstupný súbor 1: VSTUP.IN
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

 

Obrazovka testu: 1
~~~~~~~~~~~~~~~~~~~~~~~~#######~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~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 '~' )