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 = Ax 2 + 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 = 2x 2 + 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
        ikarus
         karu
         karussell
          aru
           russell
            uss
              sell