Ioi2011.or.th

International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Võidusõit
Samaaegselt IOI-ga korraldab Pattaya linn võidusõidu International Olympiad in Racing (IOR) 2011. Korraldajana peame leidma võidusõiduks parima marsruudi. Pattaya-Chonburi linnastus on N linna, mis on omavahel seotud N-1 maanteest koosneva
teedevõrgustikuga. Kõik maanteed on kahesuunalised, ühendavad kaht erinevat linna ja on täisarv
kilomeetrit pikad. Iga kahe linna vahel on täpselt üks võimalik marsruut. See tähendab, et on ainult
üks võimalus liikuda ühest linnast teise läbi maanteede jada ilma ühtegi linna teist korda läbimata.
IOR-i reeglid nõuavad, et võistlusraja pikkus peab olema täpselt K kilomeetrit ning see peab
algama ja lõppema erinevates linnades. Õnnetuste vältimiseks ei tohi rada läbida ühtki maanteed (ja
sellest tulenevalt ka ühtki linna) rohkem kui ühe korra. Liikluse minimaalseks häirimiseks peab rada
koosnema võimalikult vähestest maanteedest.
Ülesanne
Kirjutage meetod best_path(N,K,H,L), millele antakse ette järgnevad parameetrid:
 N – linnade arv; linnad on nummerdatud 0 kuni N-1.
 K – nõutud raja pikkus.
 H – maanteid kirjeldav kahemõõtmeline massiiv; iga 0 ≤ i < N-1 korral ühendab maantee i
linnu H[i][0] ja H[i][1].
 L – maanteede pikkusi kirjeldav ühemõõtmeline massiiv; iga 0 ≤ i < N-1 korral on maantee
i pikkus L[i].
Võite eeldada, et kõik väärtused massiivis H on lõigust 0 kuni N-1 ja selle massiivi poolt
kirjeldatavad maanteed ühendavad omavahel kõiki linnu eelpool kirjeldatud viisil. Võite eeldada, et
kõik väärtused massiivis L on täisarvud lõigust 0 kuni 1 000 000.
Teie meetod peab tagastama minimaalse maanteede arvu, mis on vajalik nõuetekohase
võidusõiduraja (pikkusega K) valimiseks. Kui sellist rada ei leidu, peab teie meetod tagastama -1.
Vaatleme joonisel 1 näidatud juhtu, kus N=4, K=3,
Rada võib alata linnast 0, sealt minna linna 1 ja lõppeda linnas 2. Selle pikkus on täpselt 1 km + 2 km = 3 km ja see koosneb täpselt kahest maanteest. best_path(N,K,H,L) peab tagastama 2.
International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Vaatleme joonisel 2 näidatud juhtu, kus N=3, K=3,
Ühtegi nõuetekohast rada ei ole. Antud juhul peab best_path(N,K,H,L)
tagastama -1.
Vaatleme joonisel 3 näidatud juhtu, kus N=11, K=12,
Üks võimalik rada koosneb 3-st maanteest: linnast 6 läbi linnade 0 ja 2 linna 3. Teine rada algab linnast 10 ja läheb läbi linna 8 linna 6. Mõlemad rajad on nõuetekohaselt täpselt 12 km pikad. Teine rada on
optimaalne, sest ei ole ühtegi ainult ühest maanteest koosnevat rada. Seega peab
best_path(N,K,H,L) tagastama 2.
Alamülesanded
Alamülesanne 1 (9 punkti)
 1 ≤ N ≤ 100
 1 ≤ K ≤ 100
 Teedevõrk moodustab lihtsaima võimaliku joone: iga 0 ≤ i < N-1 korral ühendab maantee i
linnu i ja i+1.
Alamülesanne 2 (12 punkti)
 1 ≤ N ≤ 1 000
 1 ≤ K ≤ 1 000 000
International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand
Alamülesanne 3 (22 punkti)
 1 ≤ N ≤ 200 000
 1 ≤ K ≤ 100
Alamülesanne 4 (57 punkti)
 1 ≤ N ≤ 200 000
 1 ≤ K ≤ 1 000 000
Realisatsioon
Piirangud
 Protsessori ajalimiit: 3 sekundit  Mälulimiit: 256 MB Note: Magasinmälul eraldi piirangut ei ole. Magasinmälu loeb üldises mälukasutuses.
Liides (API)
 Töökataloog: race/  Võistleja lahendus: race.c või race.cpp või race.pas  Võistleja lahenduse liides: race.h või race.pas  Hindaja liides: race.h või racelib.pas  Testkeskkond: grader.c või grader.cpp või grader.pas  Testkeskkonna sisend: grader.in.1, grader.in.2, . Note: Testkeskkonna sisendi vorming:
 Rida 1: N ja K.
 Read 2 kuni N: maanteede kohta käiv informatsioon; see tähendab, et rida i+2
sisaldab tühikutega eraldatud väärtusi H[i][0], H[i][1] ja L[i] (0 ≤ i < N-1).
 Rida N+1: oodatav vastus.
 Testkeskkonna sisenditele vastavad väljundid: grader.expect.1, grader.expect.2, . Selles ülesandes peab igas failis olema tekst "Correct.".

Source: http://www.ioi2011.or.th/hsc/tasks/EST/race.pdf