Zadania krajské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),
ak robí v jazyku C/C++, vytvorte aj EXE súbor. 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. Pri určovaní postupujúcich do celoslovenského kola môžu zohrať rozhodujúcu úlohu prémiové body za kratší čas behu Vášho programu pri ostrých testoch.
Zadanie úlohy:
Záhady záhrady pána Hardyho.
Matematik G. H. Hardy zakopal vo svojej záhrade fľašu, do ktorej vložil zápis špeciálnych čísel. Hardyho čísla majú nasledujúcu vlastnosť:
(H) Číslo = Súčtu N-tých mocnín
svojich cifier
napr.: 153 = 1^3 + 5^3 + 3^3 pre
N = 3, kde ^ znamená umocnenie
Po rokoch fľašu vykopal J. F. Easy, jeden z jeho žiakov. Na svoje prekvapenie zistil, že metóda ceruzky a papiera mu nedáva možnosti preveriť výsledky svojho veľkého učiteľa. Treba použiť PC. Napíšte program, ktorý bude riešiť tieto úlohy:
0) (10 bodov) Od pozície (2,2) napíše na počesť jeho
veľkého učiteľa text:
G.H.Hardy:
'Zakopany poklad'.
a) (4 body) Prečítajte číslo N a číslo C.
Urobte kontrolné výpočty a výsledok píšte od pozície (2,4) v tvare
podľa ukážky. (1 < N < 10, 0 < C < 10^10)
b) (5 bodov) Prečítajte ďalšie číslo D, urobte
kontrolné výpočty a nájdite N, pre ktoré je splnená vlastnosť (H).
Vypíšte N od pozície (2,5). (0 < D < 10^10)
c) (6+6 bodov) Ďalšie čísla D1, D2 ho úplne šokovali -
nepodarilo sa mu nájsť vhodný exponent. Dokonca D2 obsahovalo aj písmená 'A'..'I', čo malo za následok chybu pri
čítaní. Po absolvovaní doplnkovej maturity na Bratislavskom gymnáziu (GJH)
si uvedomil, že asi určite pôjde o čísla zapísané v inej ako
desiatkovej sústave. Musí ich prečítať ako reťazce. Skúste to aj
Vy. Výsledok vypíšte od (2,6-7). Ak sa nájde pre číslo viac číselných
sústav vypíšte všetky riešenia vzostupne podľa základu číselnej
sústavy. (0 < N < 16; 2 < Základ < 21; 1 < dĺžka(D1,D2)
< 10).
d) (9 bodov) Hardyho rukopis sa stal vplyvom času nie
práve najlepšie čitateľným. Mr. Easy, ako reštaurátor rukopisu,
nedokáže prečítať jednu z cifier, tak ju nahradil '*'.
Prečítajte toto číslo (zrejme ako string), nájdite N a chýbajúcu
cifru a výsledok vypíšte od (2,6).(počet znakov < 10)
Zázraky Hardyho záhrady si bola pozrieť aj skupina KSP. Keď študovali plán záhrady, Julka zvolala: Všimnite si túto skupinku troch stromov, tvoria Hardyho číslo! Naozaj na pláne sa dívali na tri štvorčeky označené ciframi 704. Tieto cifry nám dávajú: 343 + 0 + 64 = 407, čo je Hardyho klasické číslo. KSPáci skončili v najbližšom pube (t.j. pivárni) a naozaj uznali, že Julka mala pravdu. Každá súvislá skupinka stromov skrývala Hardyho číslo (a niektoré aj dve!) v desiatkovej sústave a boli to skutočne perly. Najväčšie malo skoro 200 cifier!. Situáciu komplikovala skutočnosť, že niektoré stromy podľahli zubu času a na pláne sú zakreslené iba ich pne, a teda nevieme, aké cifry predstavujú.
Prečítajte zo vstupu plán záhrady: Najskôr rozmery N,M (počet riadkov a počet stĺpcov, N,M < 45) a potom mapu znakov. Jednotlivé znaky predstavujú:
'0'..'9' .. rozličné druhy
stromov ('7' označuje lipu)
'.' .. volné miesto
'c' .. plazivka Conwayová
'P' .. plot celý obvod a nielen
to
'j' .. jahoda
'X' .. peň stromu
'f' .. miesto, kde bola
zakopaná fľaša
'M' .. začiatok vpádu
kobylky mongolskej
Následne riešte
tieto ďalšie úlohy:
e) (3 body) Nájdite súradnice zakopanej fľaše a
vypíšte od (2,10)
f) (3+5 body) Spočítajte koľko je stromov a nájdite
súradnice 3 lipiek a to východo-severnej, severo-západnej a juho-západnej a
vypíšte od (2,11) a (2,12).
g) (6 bodov) Zistite počet súvislých skupín stromov
(najviac 6) a vypíšte od pozície (2,13). Ak sa vám podarí zistiť aké
Hardyho čísla predstavujú, vypíšte ich postupne od (2,14) do každého
druhého riadku v poradí akom sa vyskytnú pri postupnom prehľadávaní
riadkov a stĺpcov (ak skupina predstavuje dve 'perly', vypíšte menšie
číslo). Každá 'perla' bude ocenená za 6 bodov. (Súvislosť
štvorčekov plánu chápeme v 4 smeroch, skupina sa dá vypísať do dvoch
riadkov obrazovky. ) V Hardyho denníku sme našli tieto tvrdenia: Exponent
N > dĺžka perly-2; Ak Exponent N = dĺžke perly, tak dĺžka <
40.
h) (8 bodov) V záhrade si žije kobylka jahodová, skáče z
jahôdky na jahôdku (rovno cez dva štvorčeky a potom jeden vľavo alebo
vpravo, presne tak ako v šachu a nikdy inak. Keď sa chce dostať na
jahôdku, ktorá neodpovedá tomuto pravidlu, musí sa preplaziť po zemi).
Najmenej koľkokrát musí zoskočiť kobylka na zem, keď chce
navštíviť všetky jahody? Výsledok od (36,9).
i) (5 bodov) Koľko najviac jahôdok dokáže navštíviť
kobylka bez lezenia po zemi, keď začne od severo-západnej jahody?
Výsledok od (36,10).
j) (8 bodov) Záhradu prepadla kobylka mongolská, prišla z
východu a každým skokom postupovala na západ (o jeden alebo dva štvorčeky
podľa šachových pravidiel) na rozdiel od kobylky jahodovej skáče aj
po zemi. Koľko najviac jahôdok mohla navštíviť (a teda
zlikvidovať)? Výsledok od (36,11). (môže skočiť na
ľubovoľný štvorček plánu, teda aj na 'P', 'X'..)
k) (12 bodov) Plazivka Conwayová sa šíri veľkou
rýchlosťou, ale aj rýchlo vymiera a to všetko podľa pravidiel, ktoré
zistil matematik N. Conway. Život plazivky závisí od ôsmich susedných
štvorčekov. Ak plazivka nemá práve dva alebo tri susedné štvorčeky obsadené
plazivkou - hynie. Šíri sa na prázdny štvorček práve vtedy, ak s ním
susedia 3 štvorčeky obsadené plazivkou. Tieto magické pravidlá sa
uplatňujú presne o polnoci.
Príklad:
pred 24:00 po
0:00
....cc.....c. ...........cc
.c.....1...cc .......1...cc
.c....ccc.... ccc....c.....
.c..........c .......c.....
prečítajte
číslo T a od pozície (36,13) vypíšte počet štvorčekov obsadených
plazivkou o T dní (T < 1111).
l) (10 bodov) Na záhrade žije krtko lipkový. Jeho 3
chodbičky musia vychádzať zo zeme pod koreňmi 3 lipiek, ktorých
súradnice sme zistili v úlohe f). Kde si má vybudovať krtko svoj brlôžtek,
aby dĺžka 3 chodbičiek ku 3 lipkám bola čo najmenšia? Výsledok
od (36,12).
.......................................................................................................................................................
Ukážka toho,
čo by mal obsahovať Váš program:
uses uHardy, crt;
const MaxX = 45; MaxY = 45; MaxD = 150; MaxJ = 240; MaxT = 1111;
var N, C, D, T, M, i : integer;
D1, D2, Rest : string;
A : array[1..MaxY] of
string[MaxX];
begin
assign( input, 'test.in'); reset( input );
readln( N, C, D );
.... ulohy a,b) ...
readln( D1 );
readln( D2 );
.... uloha c) ...
readln( Rest );
.... uloha d) ...
readln( N, M );
for i := 1 to N do readln(A[i]);
..... ulohy
e,f,g,h,i,j,l)...
read(T);
..... uloha k) ...
end.
3 153
371
200
11AA
14*59929
11 17
PPPPPPPPPPPPPPPPP
P74..c...j.jcc..P
P94j14.j1X3X7j.MP
P..j4j..1.j.1...P
P.9992..11250.j.P
P.5.j..23..jj...P
P.j....3........P
P.ccc...j07..ccfP
P.....j...4.c..cP
P...j........cc.P
PPPPPPPPPPPPPPPPP
55
obrazovka
testu: 1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~G.H.Hardy:~'Zakopany~poklad'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~N:3~153=1+125+27~OK.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~N:3~371=27+343+1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~N:5~200~zaklad:~4~~N:7~200~zaklad:~8~~N:9~200~zaklad:~16~~~
~N:3~11AA~zaklad:~12~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~14*59929=>14459929~pre~N:~7~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Zoskoci:~1~~~~~~~~~~~~~~~
~Flasa:~(16;8)~~~~~~~~~~~~~~~~~~~~~Navstivi:~13~~~~~~~~~~~~~
~Stromy:~30~~~~~~~~~~~~~~~~~~~~~~~~Mongol:~9~~~~~~~~~~~~~~~~
~Lipky:~(13;3)(2;2)(11;8)~~~~~~~~~~Krtko:~(10;5)~~~~~~~~~~~~
~P~e~r~l~y:~4~~~~~~~~~~~~~~~~~~~~~~Conway:~9~~~~~~~~~~~~~~~~
~9474~pre~N:~4~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~14459929~pre~N:~7~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~233411150132317~pre~N:~17~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~407~pre~N:~3~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Výpis je iba na
šírku 60, medzery sú vypisované ako '~'. Ak si chcete svoj program
otestovať použite UNIT uHardy (tento unit Vám pripraví aj vstupný súbor).
Po skončení sa výsledky pripisujú do súboru 'v.pas'.
3 154
374
206
11AA5
14*59919
20 17
PPPPPPPPPPPPPPPPP
P74..c...j.jccM.P
PXXj14..1X3X7...P
P...4...1.j.1...P
P.9992..11250...P
P.5....23...f...P
P.j.17.3........P
P51724..........P
P...............P
P...............P
P....ccc........P
P....ccc........P
P....ccc........P
P.......ccc.....P
P.......ccc.....P
P...... ccc.....P
P...............P
P.............X.P
P.............04P
PPPPPPPPPPPPPPPPP
999
obrazovka
testu: 2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~G.H.Hardy:~'Zakopany~poklad'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~N:3~154=1+125+64~Error~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Neexistuje~N~pre:~374~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Neexistuje~sustava~pre:~206~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Neexistuje~sustava~pre:~11AA5~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~14*59919~Neexistuje~N~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Zoskoci:~2~~~~~~~~~~~~~~~
~Flasa:~(13;6)~~~~~~~~~~~~~~~~~~~~~Navstivi:~3~~~~~~~~~~~~~~
~Stromy:~37~~~~~~~~~~~~~~~~~~~~~~~~Mongol:~3~~~~~~~~~~~~~~~~
~Lipky:~(13;3)(2;2)(4;8)~~~~~~~~~~~Krtko:~(5;5)~~~~~~~~~~~~~
~P~e~r~l~y:~5~~~~~~~~~~~~~~~~~~~~~~Conway:~12~~~~~~~~~~~~~~~
~9474~pre~N:~4~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~14459929~pre~N:~7~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~233411150132317~pre~N:~17~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~1741725~pre~N:~7~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~407~pre~N:~3~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~