Eesti koolinoorte matemaatikaolümpiaadidid Eesti koolinoorte informaatikaolümpiaadid Eesti koolinoorte füüsikaolümpiaadid Eesti koolinoorte keemiaolümpiaadid Astronoomiahuvilistele Eesti koolinoorte bioloogiaolümpiaadid Eesti koolinoorte geograafiaolümpiaadid Täppisteaduste Kooli informaatikaosakond

1995.-1996. õppeaasta

IOI kandidaatide katsevõistluse 2. päeva ülesanded


1. Osta odavalt, osta odavamalt ( 40 p. )

Nõuanne "Osta odavalt" on pool üldisest aktsiaturul õnnestumise valemist. Kuid selleks, et olla hea investeerija, peab arvestama ka järgmise nõuandega: "Osta odavalt, osta odavamalt".

See tähendab, et iga kord, kui Te ostate aktsiaid, peab hind olema odavam eelmisel ostmisel kehtinud hinnast. Mida rohkem kordi Te suudate suudate osta odavamalt kui enne, seda paremaks investeerijaks saab Teid pidada.

Teile on antud aktsiate müügihinnad päevade kaupa pikema perioodi vältel. Osta võib aktsiaid iga päev, pidage ainult meeles, et iga kord, kui Te ostate, peab hind olema odavam eelmise ostmise ajal kehtinud hinnast. Ülesandeks on kirjutada programm, mis teeks kindlaks need päevad, millal Te peate aktsiaid ostma, selleks et maksimiseerida ostukordade arvu.

Näiteks IBM aktsiate hinnad järjestikulistel päevadel on järgmised:

Päev 1 2 3 4 5 6 7 8 9 10 11 12

Hind 68 69 54 70 68 64 70 62 67 78 98 87

Selle näite korral parim investeerija saab osta vähemalt 4 korda. Need 4 päeva on:

Päev 4 5 6 8

Hind 70 68 64 62

Sisendandmed: Hinnad on salvestatud tekstifaili, mille esimesel real on päevade arv N (N <= 1000). Näide (fail O.0):

12
68
69
54
70
68
64
70
62
67
78
98
87

Väljundandmed: Väljastage väljundfaili O.OUT 1) pikima valitud järjestuse pikkus ja 2) sellise pikkusega erinevate järjestuste arv.

Näiteks:

Osta saab 4 korda

Selliseid ostmiseviise on 2

Järjestused, mille tulemuseks on ühesugune hindade jada, tuleb lugeda samasugusteks ja loetakse ühe lahenduse ette.


2. Ruutparabool ( 20 p. )

Tekstifailis on kolme tasandipunkti koordinaadid (reaalarvud, igal real üks punkt). Leida sellised arvud A, B ja C, et ruutparabool y = Ax2 + Bx + C läbib neid punkte (lahendades vastava kolme tundmatuga lineaarse võrrandisüsteemi). Tulemus kirjutada faili R.OUT.

Näide: Failis R.0 on punktid, mida läbib parabool y = 2x2 + 3x - 1:

0 -1
1 4
10 229


3. SPIRAALMÕISTATUS ( 40 p. )

Spiraalmõistatuse täislahenduseks on string, milles mõistatuse küsimuste vastused asuvad mingitel kindlatel positsioonidel. Näiteks võib selleks olla string matemaatikarussell, milles küsimuste vastused on kohtadel 1-2, 1-11, 3-6, 3-11, 5-7, 10-13, 10-18, 12-18, 13-15, 15-18. Sealjuures on vastused omavahel põimitud, nii et iga küsimuse vastuses kuulub vähemalt esimene täht ka mingile eespool olevale ja viimane täht mingile tagapool jätkuvale vastusele (v.a. lahenduse algus ja lõpp).

Tekstifailis on esimesel real küsimuste arv (mitte üle 20), järgmistel ridadel ühekaupa küsimuste vastused mingis järjekorras (sõnad koosnevad väikestest ladina tähtedest, pikkusega kuni 15) .

Leida minimaalse pikkusega täislahendus, mis sisaldab neid vastuseid. Väljundfaili S.OUT kirjutada eraldi ridadele täislahenduse alla vastavatele positsioonidele sisendist saadud sõnad.

Näide: Fail S.0 :

13
aru
ema
ikarus
karu
karussell
ma
maa
matemaatika
russell
sell
tema
temaatika
uss

ja vastav väljundfail S.OUT:

matemaatikarussell
ma
matemaatika
tema
temaatika
ema
maa
karu
karussell
aru
russell
uss
sell


Palume saata kõik küsimused aadressil ttkool@ut.ee
Viimati muudetud: 01.04.1999. a.