1995.-1996. õppeaasta

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

1. Sõbralikud arvud ( 20 p. )

Arve 220 ja 284 nimetame 'sõbralikeks arvudeks' sellepärast, et mõlema korral on temast endast erinevate jagajate summaks teine arv. See tähendab, et

arvu 220 tegurite summa 1+ 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 on 284 ,

arvu 284 tegurite summa 1 + 2 + 4 + 71 + 142 on 220 .

Sisendfailis on arv N . Kirjutada väljundfaili esimesele reale N ja järgmistele ridadele kõik teineteisest erinevate sõbralike arvude paarid X,Y (üks paar reale), kus X,Y ≤ N.

Programm peab töötama võimalikult suure N korral .

2. Uued liinid ( 30 p. )

Seitsme mäe ja mere taguses kuningriigis sai sideminister käsu ühendada kõik linnad uute sideliinidega. Et sideminister oli majanduslikult mõtlev mees, siis leidis ta, et kaks linna on ühendatud, kui ühest linnast teise on võimalik saata teateid üle naaberlinna(de). Sellegipoolest ehitab ta liine ainult otse linnast linna. Pärast mõningast arvutamist leidis ta linnade ühendamiseks vajamineva kaabli minimaalse kogupikkuse.

Sisendfaili esimesel real on kirjas linnade arv ja iga järgmine rida sisaldab mingi linna asukoha täisarvulisi x ja y koordinaate. Leida vajalik kaabli pikkus. Linnu ei ole rohkem kui 1000 .

Näide . Sisendfail L.0, mille puhul vastus on 12.0.

6
4 7
7 5
7 3
4 5
9 8
9 5

3. Lipustuv ettur ( 50 p. )

Malelauale on paigutatud mõned valged vigurid (maksimaalselt lipp, 2 vankrit, 2 erivärvilist oda ja 2 ratsut) ja must ettur (võib olla ridadel 2-6). Kuningaid ei ole. Kõik malendid teevad oma tavalisi käike ja lööke.

Valge saab R punkti, kui ta lööb musta malendi R-ndalt realt,

0 punkti, kui must ettur ei saa tema ees oleva valge malendi tõttu teha järjekordset käiku,

-5 punkti, kui must saab pärast 1. real viguriks muundumist teha veel ühe käigu.

Leida maksimaalne tulemus, mida valge võib saada. Mittenegatiivse tulemuse korral väljastada ka seisud iga valge käigu järel juhuks, kui must ei löö kordagi.

Näide : Sisendfailile M.0 vastav väljundfail. Vasakpoolne malelaua kujutis on algseis sisendfailis. Järgnevad 2-veeruste vahedega seisud pärast valge esimest, teist jne. käiku.

 abcdefgh     abcdefgh     abcdefgh     abcdefgh
8 # # # #8   8 # # # #8   8 # # # #8   8 # # # #8
7# # # #R7   7# # # # 7   7# # # # 7   7# # # # 7
6 # # # #6   6 # # # #6   6 # # # #6   6 # # # #6
5# E # # 5   5# E # R 5   5# # # # 5   5# # # # 5
4 # # # #4   4 # # # #4   4 #E#R# #4   4 # # # #4
3# # # # 3   3# # # # 3   3# # # # 3   3# R # # 3
2 # # # #2   2 # # # #2   2 # # # #2   2 # # # #2
1# # # # 1   1# # # # 1   1# # # # 1   1# # # # 1
 abcdefgh     abcdefgh     abcdefgh     abcdefgh