Zadania Krajského kola súťaže ZENIT v programovaní
v školskom roku 2005/2006 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íte 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
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:
Ujo Fero ide do Iraku.
Ujo Fero ma
nastúpiť ako matematik slovenskej vojenskej jednotky v Iraku. Do odchodu mu
ostáva málo času. Musí toho ešte veľa do konca školského polroku urobiť a
vyriešiť. Dúfa pevne, že mu pomôžete. Riešte s ním a pre neho tieto
urgentné úlohy:
0)
(10
bodov) Od pozície (2,2)
napíše: 'Odlet je tu! Ujo
Fero ponahlaj sa!'.
a) (10+5+12+10+5 bodov) Treba pripraviť počítačové spracovanie
údajov pre polročné vysvedčenia. Prečítajte N = počet žiakov a pZ = počet známok. Potom prečítajte známky
(prvá zo známok je správanie) pre
každého žiaka. Okrem známok prečítajte aj absenciu (vymeškané hodiny celkom
a z toho neospravedlnené). Každému žiakovi vypočítajte priemer a určite
jeho celkový prospech. Program musí brať do úvahy, že 10 a viac hodín
neospravedlnenej absencie automaticky znamená, zhoršenie známky zo správania z
1 na 2 (teda zmenu oproti vstupu). Formát vstupu a výstupu je daný ukážkami.
Pravidlá na určenie celkového prospechu:
VZ .. prospel s vyznamenaním, správanie 1, nemá
známku horšiu ako 2 a priemer <=
1.50.
VD .. prospel veľmi dobre, správanie 1, nemá
známku horšiu ako 3 a priemer <= 2.00 .
P ..
prospel nemá žiadnu 5.
NP .. neprospel má aspoň jednu 5.
Medzi známkami a menom, menom a priezviskom je
práve 1 medzera. Známky vypisujte od 54. stĺpca, priemer od 65. stĺpca a celkový prospech od 78. stĺpca. Ak je
priezvisko dlhšie skráťte jeho výpis na 12 znakov. Na vstupe je meno a
priezvisko, prvé písmena sú veľké, na výstupe je priezvisko a iba prvé písmeno
mena! Výpis začína od pozície (40,1-25). Ak by bolo žiakov viac ako 25,
vypíšeme iba prvých 25.
b) (9+6+7+9 bodov) Dôležitá je aj štatistika celkového prospechu. Vypíšte ju podľa ukážky od pozície (2,4-7). Od pozície (2,8) vypíšte
celkovú a priemernú absenciu a od pozície (2,9) priezvisko najväčšieho
absentéra ( ak ich je viac, tak iba prvého poznámku :'a spol. '). Podobne
vypíšte aj čistých jednotkárov od pozície (2,10).
c) (10+12+12+17 bodov) Jednou z hlavných úloh Uja Fera
v Iraku je nájdenie optimálneho
(najlepšieho) riešenia úloh našej jednotky. V prvom rade je to
odstránenie mín z ropnej oblasti. Fero má pred sebou mapu a dumá: "Mám tu
N ropných studní, medzi nimi je M priamych ciest, ja by som povedal
úsečiek". Ešte vidím, že tieto studne neležia na jednej priamke. Súradnice
GPS sú tu pekne prerátané na pravouhlé súradnice x, y. Potrebujem zrátať dĺžku
všetkých úsečiek a vypísať od pozície (2,12). Ďalej použijem pravidlo:
každú studňu spoj s k nej najbližšou (ak ešte nie je medzi nimi
prepojenie). Dĺžku týchto ciest (úsečiek) spočítam a vypíšem od (2,13).
Hm, hm takto sa mi ale nemusí podariť spojiť všetky studne.., a vidím, že sa to
rozpadne na K súvislých častí toto číslo vypíšem od (2,14). Na koniec to treba
pospájať celé dohromady a dostanem celkovú dĺžku minimálnej siete a tú vypíšem na (2,15). Bez ohľadu na tieto špekulácie uja Fera (alebo podľa
nich!) nájdite koľko najmenej meria také prepojenie týchto studní, aby sa z
každej dalo dostať do ľubovolnej inej (podľa uja Fera na to stačí práve N-1
úsečiek). Tieto ujo Fero prikáže odmínovať naším nebojácnym vojakom. Prečítajte
N, M a následne N dvojíc súradníc
(x,y) pre studne a M dvojíc (z,k) pre M
ciest, kde z, k sú čísla studní, medzi ktorými existuje priama cesta -
úsečka.
d) (6+5+25 bodov) Ešte odo mňa chcú aby som našiel najmenší
obdĺžnik so stranami rovnobežnými s osami x, y tak, aby všetky studne boli
v jeho vnútri a ich vzdialenosť od obvodu (budeme stavať ochranný
plot proti teroristom!) bola najmenej 1. Toto je „very ízy“ hovorí si Ferko
napíšem to ako súčin dvoch jednorozmerných intervalov od pozície (2,16). Plot postavený podľa tohto obdĺžnika
má dĺžku:.. a tú napíšem od pozície (2,17). Dalo by sa krásne ušetriť, keby som
miesto obdĺžnika použil dlhú gumičku, tá by sa natiahla do tvaru konvexného
polygónu a všetko by bolo dnu, ale musel by som vo vrcholoch urobiť oblúčiky
o polomere 1 .. obvod oblúčikov si trúfam vyrátať, však som predsa nejaký
ten Matematik a spolu to bude.. a to vypíšem od pozície (2,18).
„Tak to ale bola fuška..“ hovorí si Ujo Fero. „A
teraz sa budeme konečne venovať vede“:
e) (8+10+10 bodov)
Vytvorím takúto postupnosť: Začnem s číslom Z,
spočítam jeho cifry a ďalší člen dostanem odpočítaním tohto súčtu cifier od Z. Určite sa dostanem
postupne k nule. Koľko krokov na to musím urobiť? Prečítaj zo vstupu Z a vypočítaj prvé
dva členy tejto postupnosti spolu s počtom krokov k nule vypíš od pozície
(2,20). Podobne to zrátaj aj v binárnej a hexadecimálnej sústave. Výsledok vypíš od
pozície (2,21-22).
f) (10+15 bodov) Koľko je
dvojíc celých čísiel x < y ktoré
patria do daného intervalu (zac,kon)
tak, aby bol vyraz x^2 + y^2 deliteľný 49 bezo zvyšku? Prečítajte zo vstupu
zac, kon. A výsledok píšte od pozície (2,23). Veľmi by mi pomohlo v mojej
vedeckej práci, keby ste zistili, pre ktorú preponu C z tohto intervalu
existuje najviac pravouhlých Pytagorejských 3uholníkov. Výsledok píšte od
pozície (2,24). Ak ich je viac, vypíš najmenšiu.
g) (17 bodov) Ďalší
vedecký problém je zistenie počtu postupností podľa daných podmienok. Koľko je
postupností z písmeniek A,B keď vieme, že za sebou ide dvojica 'AA' práve
pocAA krát, dvojica 'AB' pocAB krát a
podobne máme dané pocBA a pocBB. Napríklad pre postupnosť: AABABBB máme:
pocAA =
1 pocAB = 2 pocBA = 1 pocBB = 2
ľahko zistíme, že počet rôznych takýchto
postupností je 6. Prečítajte zo vstupu čísla: pocAA, pocAB, pocBA a pocBB
zistite pomocou PC (alebo podľa vzorca vypočítajte) počet týchto postupnosti a
výsledok píšte od pozície (2,25).
Váš program by mal obsahovať tieto základne prvky:
uses uKraj, crt;
var x,y : array[1..111] of integer;
z,k : array[1..333] of integer;
zn : array[1..10] of integer;
begin
clrscr;
assign( input, 'VSTUP.in' );
reset( input );
..... ... Tvoj
program - čítanie dát
a Tvoje výpočty
end.
13 9 N < 40 pZ < 11
1 2 3 4 1 1 1 1 1 1 7 0 Zuzana
Bakova
2 1 2 2 1 1 2 2 1 1 60 0 Jana
Fialova
1 3 4 3 3 2 3 4 5 1 30 0 Anna
Hajokova
1 2 1 1 1 1 1 1 1 1 20 10 Boris
Hruzik
1 2 3 2 1 1 1 1 1 1 14 3 Dusan
Hupka
2 1 1 1 1 1 1 1 1 1 0 0 Juro
Kovac
1 2 3 2 3 1 1 1 1 1 4 3 Stefan
Maly
1 2 3 2 2 2 2 1 1 1 17 0 Barboa
Michalovcikova
1 2 3 2 3 1 1 1 1 1 60 3 Pavol
Mraz
1 1 1 1 1 1 1 1 1 1 4 0 Peter
Mraz
1 1 2 2 1 1 3 4 1 1 50 0 Igor
Potz
1 1 1 1 1 1 1 1 1 1 0 0 Janko
Usilovny
1 1 1 1 1 2 3 1 1 1 0 0 Juraj
Usilovny
12 22 N < 111
M < 333
11 13 15 11 17 11 súradnice -1000 < x,y < 1000
19 12 17 13 13 13
13 14 15 14 16 14
17 14 14 12 15 12 cesty:
1 2 1 11 1 6
1 7 2 11
2 3 2 5 3 4 3 5
4 10 4 5 5 10 5 12
6 11 6 7 6 8
8 9 8 12 8 11
8 5 9 10 10 12
18 Z < 64000
325 325 zac,kon < 10000000
1 2 1 2 pocAA,pocAB,pocBA,pocBB <
8
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Bakova~Z.~~~~~1234111111~~1.67~7/0~~~~P~~
~Odlet~je~tu!~Ujo~Fero~ponahlaj~sa!~~~~Fialova~J.~~~~2122112211~~1.44~60/0~~~P~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Hajokova~A.~~~1343323451~~3.11~30/0~~~NP~
~VZ:~~2~~18.18~%~~~~~~~~~~~~~~~~~~~~~~~Hruzik~B.~~~~~2211111111~~1.11~20/10~~P~~
~VD:~~3~~27.27~%~~~~~~~~~~~~~~~~~~~~~~~Kovac~J.~~~~~~2111111111~~1.00~0/0~~~~P~~
~P:~~~5~~45.45~%~~~~~~~~~~~~~~~~~~~~~~~Maly~S.~~~~~~~1232311111~~1.67~4/3~~~~VD~
~NP:~~1~~~9.09~%~~~~~~~~~~~~~~~~~~~~~~~Michalovciko~B1232222111~~1.78~1/0~~~~VD~
~Absencia:~176~na~ziaka:~16.0~~~~~~~~~~Mraz~P.~~~~~~~1111111111~~1.00~4/0~~~~VZ~
~Absenter:~Fialova~~~~~~~~~~~~~~~~~~~~~Potz~I.~~~~~~~1122113411~~1.78~50/0~~~P~~
~Same~1:~Mraz~+~spol.~~~~~~~~~~~~~~~~~~Usilovny~J.~~~1111111111~~1.00~0/0~~~~VZ~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Usilovny~J.~~~1111123111~~1.33~0/0~~~~VD~
~Dlzka~ciest:~46.60~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~K~najblizsej:~12.65~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Suvisle~casti:~4~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Min.~prepojenie:~17.06~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Obdlznik:~(10;20)x(10;15)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Plot:~30~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Polygon:~24.06~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~18~9~~kroky:~2~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~10010(2)~10000(2)~~kroky:~9~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~$12~$F~~kroky:~2~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~49:~3~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Pytagorejske~3u:~7~pre:~325~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~Pocet~post.:~6~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
( výpis je iba na
šírku 80, medzery sú
vypisované ako '~' )