PROGRAMMEERIMISOLÜMPIAADI LÕPPVOOR 14.03.1998

NOOREM RÜHM (kuni 10. klass)

1. "ROHELINE LAINE"		30 punkti	5 sekundit

Auto sõidab punktist A punkti B mööda teed, millel on N foori. Iga foor 
töötab kindla graafiku järgi, näidates P sekundit punast tuld, seejärel R 
sekundit rohelist tuld, seejärel jälle P sekundit punast tuld jne. Igal 
keskööl tehakse fooridele algkäivitus ja nad alustavad tööd punase tule 
süütamisega. Kui auto jõuab foori alla hetkel, kui seal põleb või süttib 
punane tuli, ei või ta edasi sõita. Kui auto jõuab foori alla hetkel, kui 
seal põleb või süttib roheline tuli, sõidab ta peatumata edasi. Kirjutada 
programm, mis leiab, millisel hetkel peab auto välja sõitma, et ta satuks 
"rohelisse lainesse", st sõidaks kõigi fooride alt ilma peatumata läbi.

Sisend: Tekstifaili FOOR.SIS esimesel real on auto teele jäävate fooride arv 
N (0 <= N <= 100) ja järgmisel N real igaühel kolm tühikutega eraldatud 
täisarvu. Esimene arv (Ki, 0 <= Ki <= 1000) näitab, mitu sekundit kulub 
punktist A startinud autol selle foorini jõudmiseks, kui ta ei pea teel ühegi 
teise foori taga ootama. Teine arv (Pi, 0 <= Pi <= 60) näitab, mitu sekundit 
järjest põleb selles fooris punane tuli. Kolmas arv (Ri, 0 <= Ri <= 60) 
näitab, mitu sekundit järjest põleb selles fooris roheline tuli. Arvud Ki on 
kõik erinevad ja read on failis nende kasvamise järjekorras.

Väljund: Tekstifaili FOOR.VAL esimesele reale väljastada täisarv, mis 
näitab, mitu sekundit pärast fooride käivitamist peab auto punktist A välja 
sõitma, et ta satuks "rohelisse lainesse". Väljastada tuleb vähim võimalik 
arv (või -1, kui "rohelist lainet" ei olegi).

Näide:
	FOOR.SIS	FOOR.VAL
	3		40
	110 30 30
	250 40 20
	350 20 20

2. AKNAHALDUR			30 punkti	5 sekundit

Arvuti ekraanil on teatav hulk aknaid, mis võivad üksteist osaliselt või 
täielikult katta. Kasutaja juhib akende paigutust ekraanil hiire abil. Vasaku 
hiirenupu klõpsutamine mingis aknas tõstab selle akna kõige pealmiseks, 
parema hiirenupu klõpsutamine aga viib akna kõige alumiseks. Kirjutada 
programm, mis leiab akende esialgse paigutuse ja kasutaja poolt tehtud 
hiireklõpsude põhjal akende lõpliku paigutuse ekraanil.

Sisend: Tekstifaili AKEN.SIS esimesel real on ekraanil olevate akende arv N (0 
<= N <= 100) ja järgneval 2*N real on akende andmed, iga akna andmed kahel 
real. Esimesel real on akna nimi (string pikkusega <= 40 sümbolit) ja teisel 
real neli tühikutega eraldatud täisarvu Xi1, Yi1, Xi2, Yi2. (Xi1, Yi1) on 
akna vasaku ülemise ja (Xi2, Yi2) parema alumise nurga koordinaadid (0 <= 
Xi1<Xi2 <= 1000, 0 <= Yi1<Yi2 <= 1000). Akende andmed on failis nende sügavuse 
kasvamise järjekorras (st kõige pealmine aken esimesena). Tekstifaili 
HIIR.SIS esimesel real on kasutaja tehtud hiireklõpsude arv K (0 <= K <= 1000) 
ja järgmisel K real igaühel kolm tühikutega eraldatud täisarvu Xj, Yj, Zj, 
kus (Xj, Yj) on hiirekursori koordinaadid klõpsutamise hetkel (0 <= Xj <= 
1000, 0 <= Yj <= 1000) ja Zj on 0, kui klõpsutati vasakut hiirenuppu ning 1, 
kui klõpsutati paremat hiire-nuppu. Iga hiirenupu klõpsutamine mõjub kõige 
pealmisele aknale, mille sees hiirekursori koordinaadid klõpsutamise hetkel on 
(akna ääred loetakse akna sisse kuuluvaks). Hiire klõpsutamine kõigist 
akendest väljapoole jääval ekraaniosal ei oma mingit mõju.

Väljund: Tekstifaili AKEN.VAL väljastada akende nimed nende sügavuse 
kasvamise järjekorras (st kõige pealmine aken esimesena) vastavalt nende 
lõplikule paigutusele. NB! Aknaid tegelikult ekraanile MITTE JOONISTADA!

Näide:
	AKEN.SIS	HIIR.SIS	AKEN.VAL
	3		5		Kolmas Aken
	Esimene Aken	500 200 1	Teine Aken
	300 100 600 300	100 200 0	Esimene Aken
	Teine Aken	300 300 0
	200 200 500 400	500 500 1
	Kolmas Aken	100 500 0
	100 300 400 500

3. KLEEPRIBAD			40 punkti	5 sekundit

Paberile on trükitud ühe või enama tühikuga eraldatud arvudest koosnev 
rida, kus arvud koos-nevad sümbolitest 0 kuni 9. Peale selle on antud hulk 
kleepribasid, millele on otsast otsani trükitud mingi üks väike ladina täht 
(erinevatel ribadel on erinevad tähed). Kõik sümbolid (numbrid, tähed ja 
tühikud) on võrdse laiusega. Ribadega tuleb katta arve nii, et
	1) iga riba katab mingi arvu esimesest numbrist kuni mingi arvu viimase 
numbrini,
	2) ribad ei kata üksteist.
Ülesandeks on leida selline ribade kleepimise viis, et kaetud oleks 
võimalikult palju numbreid. NB! Numbreid, mitte arve!

Sisend: Tekstifaili RIBA.SIS esimesel real (pikkus <= 80) on paberile trükitud 
numbrite ja tühikute jada, kusjuures esimene ja viimane sümbol ei ole 
tühikud. Teisel real on paberiribade arv N (1 <= N <= 20). Järgmisel N real 
(igaühe pikkus <= 80) on paberiribadele trükitud tähed.

Väljund: Tekstifaili RIBA.VAL esimesele reale kirjutada sisendfaili esimene 
rida, teisele reale leitud lahendus, kujutades ribasid ribale trükitud 
tähtedega ja jättes katmata sümbolid alles, ja kolmandale reale kaetud 
numbrikohtade arv.

Näide:
	RIBA.SIS
	1 4004 303  22  1 7111117   82222228
	4
	aaaaaaaaaaaaaaaaaa
	bbbbbbbbbb
	cccc
	dd

	RIBA.VAL
	1 4004 303  22  1 7111117   82222228
	1 cccc aaaaaaaaaaaaaaaaaa   82222228
	17

Hindamine: Iga testi punktide arvu määrab vastuses kaetud numbrite arvu 
protsent parima võimaliku paigutuse korral kaetud numbrite arvuga võrreldes. 
Näites toodud vastus saaks 68 protsenti selle testi võimalikest punktidest, 
sest parim kate on
	1 4004 303  22  1 7111117   82222228
	bbbbbbbbbb  dd  1 aaaaaaaaaaaaaaaaaa
	25
Kui leitud kate ei vasta ülesande tingimustele (ribade pikkusi on muudetud, 
nad ei alga arvude alguses, ei lõpe arvude lõpus vms), antakse selle testi 
eest 0 punkti.

VANEM RÜHM (11.-12. klass)

1. "ROHELINE LAINE"		30 punkti	5 sekundit

Auto sõidab punktist A punkti B mööda teed, millel on N foori. Iga foor 
töötab kindla graafiku järgi, näidates P sekundit punast tuld, seejärel R 
sekundit rohelist tuld, seejärel jälle P sekundit punast tuld jne. Igal 
keskööl tehakse fooridele algkäivitus ja nad alustavad tööd punase tule 
süütamisega. Kui auto jõuab foori alla hetkel, kui seal põleb või süttib 
punane tuli, ei või ta edasi sõita. Kui auto jõuab foori alla hetkel, kui 
seal põleb või süttib roheline tuli, sõidab ta peatumata edasi. Kirjutada 
programm, mis leiab, millisel hetkel peab auto välja sõitma, et ta satuks 
"rohelisse lainesse", st sõidaks kõigi fooride alt ilma peatumata läbi.

Sisend: Tekstifaili FOOR.SIS esimesel real on üks reaalarv, auto kiirus (V, 
0<V <= 100km/h). Eeldada, et auto sõidab pidevalt ja ühtlaselt selle 
kiirusega. Faili teisel real on teele jäävate fooride arv N (0 <= N <= 100) 
ja järgmisel N real igaühel kolm tühikutega eraldatud reaalarvu. Esimene arv 
(Ki, 0 <= Ki <= 1000km) näitab foori kaugust punktist A, teine arv (Pi, 0 <= 
Pi <= 60) näitab, mitu sekundit järjest põleb selles fooris punane tuli ja 
kolmas arv (Ri, 0 <= Ri <= 60) näitab, mitu sekundit järjest põleb selles 
fooris roheline tuli. Arvud Ki on kõik erinevad ja read on failis nende 
kasvamise järjekorras.

Väljund: Tekstifaili FOOR.VAL esimesele reale väljastada reaalarv, mis 
näitab, mitu sekundit pärast fooride käivitamist peab auto punktist A välja 
sõitma, et ta satuks "rohelisse lainesse". Väljastada tuleb vähim võimalik 
arv (või -1, kui "rohelist lainet" ei olegi).

Näide:
	FOOR.SIS	FOOR.VAL
	72.0		40.0
	3
	2.2 30.0 30.0
	5.0 40.0 20.0
	7.0 20.0 20.0

2. MENÜÜD			30 punkti	5 sekundit

Arvutis on menüüsüsteem, kus menüüdes on kaht liiki valikuid: käsud ja 
alammenüüd. Kasutaja liigub menüüvalikute vahel klahvide UP, DOWN, ENTER ja 
ESC abil. Klahvide UP ja DOWN abil liigub kasutaja menüüs vastavalt eelmisele 
ja järgmisele punktile. Klahvi ENTER abil valib kasutaja hetkel aktiivse 
punkti. Kui valitav punkt on alammenüü, siis avab arvuti selle menüü. Kui 
valitav punkt on käsk, siis täidab arvuti selle käsu ja jääb ootama 
järgmisi klahvivajutusi. Klahvi ESC abil sulgeb kasutaja aktiivse alammenüü 
ja naaseb enne seda avatud olnud menüüsse.

Sisend: Tekstifailis MENYY.SIS on 1 kuni 50 menüü kirjeldused kujul
	MENU menüünimi
	valik1
	valik2
	...
	END
kus menüünimi on kuni 20-sümboliline mittetühi string. Kõigi menüüde 
nimed on erinevad ja alati on failis olemas menüü nimega MAIN. Iga menüü 
koosneb 1 kuni 20 valikust, mis võivad olla kujul
	SUBMENU menüünimi
või
	COMMAND käsunimi
kus menüünimi on mõne samas failis kirjeldatud menüü nimi ja käsunimi on 
kuni 20-sümboliline mittetühi string. Sõnade MENU, SUBMENU ja COMMAND järel 
on alati täpselt 1 tühik. Tekstifaili KLAHV.SIS iga rida (ridu on kuni 1000) 
on ühte klahvivajutust kirjeldav string: UP, DOWN, ENTER või ESC. Programm 
peab lugema klahvivajutused ja interpreteerima neid järgmiselt:
	* Enne esimest klahvivajutust on avatud menüü MAIN ja aktiivne on 
selle esimene punkt.
	* Klahvi UP vajutamisel muutub aktiivseks hetkel aktiivsele punktile 
eelnev punkt; kui aktiivne on antud menüü esimene punkt, saab aktiivseks 
selle menüü viimane punkt.
	* Klahvi DOWN vajutamisel muutub aktiivseks hetkel aktiivsele punktile 
järgnev punkt; kui aktiivne on antud menüü viimane punkt, saab aktiivseks 
selle menüü esimene punkt.
	* Klahvi ENTER vajutamisel, kui aktiivne punkt on alammenüü 
(SUBMENU), avaneb see alammenüü ja aktiivseks muutub tema esimene valik.
	* Klahvi ENTER vajutamisel, kui aktiivne punkt on käsk (COMMAND), 
kirjutatakse selle käsu nimi väljundfaili.
	* Klahvi ESC vajutamisel, kui hetkel avatud menüü ei ole peamenüü 
(MAIN), sulgub hetkel avatud menüü ja aktiivseks saab enne selle menüü 
avamist aktiivne olnud menüüpunkt.
	* Klahvi ESC vajutamisel, kui hetkel avatud menüü on peamenüü 
(MAIN), muutub aktiivseks selle esimene punkt.

Väljund: Tekstifaili MENYY.VAL kirjutada täidetud käsud (so klahvi ENTER 
abil valitud menüüpunktid, mis ei ole alammenüüd) nende täitmise 
järjekorras, igaüks eraldi reale. NB! Menüüsid tegelikult ekraanile MITTE 
JOONISTADA!

Näide:
	MENYY.SIS	KLAHV.SIS	MENYY.VAL
	MENU MAIN	DOWN		Kolmas
	COMMAND Esimene	DOWN		Neljas
	SUBMENU Teine	ENTER		Esimene
	COMMAND Kolmas	UP
	END		ENTER
	MENU Teine	ENTER
	COMMAND Neljas	ESC
	COMMAND Viies	ESC
	END		ENTER

3. PARKETT			40 punkti	5 sekundit

Ristkülikukujulise saali põrand on kaetud vanaaegse ruudukujulistest 
tahvlitest parketiga, kus osa tahvleid on katki. Katkiste tahvlite asendamiseks 
on olemas teatud hulk ristkülikukujulisi sama-sugustest tahvlitest koosnevaid 
vana parketi tükke ja piiramata arv vajaliku mõõduga uusi üksikuid 
parketitahvleid. Et uued tahvlid on heledamad, tahetakse põrand remontida nii, 
et uusi tahvleid kasutatakse võimalikult vähe. Et aga vana parketti on vaja 
remondiks veel mujal, ei tohi ühtegi rist-külikut katki saagida, vaid neid 
tuleb kasutada tervelt ja täita ülejäänud augud uute tahvlitega. Muster on 
parketil selline, et ristkülikuid võib 90 kraadi pöörata.

Sisend: Tekstifaili PARKETT.SIS esimesel real on kaks täisarvu M ja N (1 <= M 
<= 60, 1 <= N <= 60), mis näitavad vastavalt parketiridade arvu saalis ja 
tahvlite arvu parketireas. Järgnevad M nullidest ja ühtedest koosnevat N 
sümboli pikkust rida, kus 1 tähistab tervet tahvlit ja 0 katkist. Järgmisel 
real on ristkülikute arv K (0 <= K <= 50) ja edasi K rida, mille esimeseks 
sümboliks on ristkülikut tähistav suur või väike ladina täht ja 
tühikutega eraldatult ristküliku mõõtmed (parketitahvlites). Erinevatel 
ridadel on erinevad tähed.

Väljund: Tekstifaili PARKETT.VAL esimesele reale kirjutada ristkülikuid 
kasutades asenda-tud parketitahvlite arv. Järgmisele M reale kirjutada leitud 
paigutus, jättes kõik sisendfaili sümbolid 1 alles, kirjutades iga 
ristkülikuga kaetavatele kohtadele seda ristkülikut tähistava tähe ja 
jättes uute tahvlitega kaetavate aukude kohale sümbolid 0.

Näide:
	PARKETT.SIS	PARKETT.VAL
	5 3		8
	100		1F0
	100		1F0
	001		GF1
	001		GF1
	000		GF0
	4
	a 2 2
	b 2 3
	F 5 1
	G 3 1

Hindamine: Iga testi eest antavad punktid määrab leitud paigutuses kasutatud 
vanade tahvlite arvu protsent võrreldes parima võimaliku paigutusega. Näites 
toodud vastuse eest saab 80 protsenti sellele testile määratud punktidest, 
sest on võimalik katta ristkülikutega 10 tahvlit. Kui väljastatud paigutus 
ei vasta ülesande tingimustele (asendatud on terveid tahvleid, ristkülikute 
kuju on muudetud vms), antakse selle testi eest 0 punkti.