Šikaniranje

Oddelek za gozdarske dejavnosti in motorni promet Mestne občine Ljubljana (MOL) slovi po srce parajoči skrbi za varnost kolesarjev. V imenu te skrbi jim povsod, kjer je to v interesu kolesarjev, odvzame prednost, jim postavlja različne ovire, viša robnike in ukinja kolesarske steze (predvsem, če je potrebno povečati število parkirišč za avtomobile). Vašemu profesorju se vsak dan orosi oko od ganjene hvaležnosti MOLu ob spominu na mesto na Večni poti, kjer so - kot je povedal MOL - kolesarjem odvzeli prednost, da jih ne bi povozil avto ali kombi, ki morda ne bi vedel, da imajo tu prednost kolesarji. (Več o tem.)

Ogrevalni del

(Tega dela naloge ne oddajaj. To je samo za ogrevanje.)

Nov pristop MOL k zagotavljanju varnosti kolesarjev bi lahko bilo postavljanje kock, kot ga kaže slika.

Napiši program, ki se začne s seznamom ovire, ki predstavlja razpored kock v obliki parov koordinat (x, y). Sledi naj spremenljivka x, ki vsebuje koordinato (stolpec) po katerem se bo peljal kolesar. Program naj izpiše koordinato y (vrstico) prve ovire, na katero bo naletel.

Program se torej lahko začne z

ovire = [(3, 9), (7, 1), (5, 9), (9, 2), (7, 3),
         (10, 5), (4, 7), (9, 8), (6, 5), (8, 6),
         (1, 5), (8, 4), (2, 3), (3, 6)]
x = 3

Pri teh podatkih izpiše 6, ker je to vrstica prve ovire v 3. stolpcu. Program naj seveda deluje tudi za poljuben drugačen razpored ovir, poljubno širino poti in koordinato x. Da preveriš, ali res deluje, poskušaj, recimo, različne x.

Obvezna naloga

(Rešitev te naloge oddaj.)

Ovire v resnici niso kocke, temveč šikane, kot so dve leti stale pred FRI in so ovekovečene v gornjem blogu. (Bile so plastične, v prihodnosti pa bi lahko bile betonske. Ker namreč niso osvetljene, se lahko zgodi, da jih kolesar ne bi videl ter se lahko zaletel vanje in jih poškodoval. Betonske so odpornejše, tako da bo kolesar lahko letel čeznje, ne da bi se jim kaj zgodilo.) Njihove pozicije zato niso opisane s seznamom parov, temveč seznamov trojk (x1, x2, y), kjer sta x1 in x2 (x1 <= x2) številki stolpca, kjer se ovira začne in konča (ovira pokriva tudi x2).

Napiši program, ki se začne s seznamom ovir in številko stolpca, na primer

ovire = [(1, 3, 6), (2, 4, 3), (4, 6, 7),
         (3, 4, 9), (6, 9, 5), (9, 10, 2), (9, 10, 8)]
x = 6

in izpiše številko vrstice s prvo oviro. Za gornji primer izpiše 5, seveda pa naj deluje tudi z drugačnimi podatki.

Predpostaviti smeš, da bo kolesar vedno naletel na oviro.

Dodatna naloga

K programu dodaj še tole: program naj najprej ugotovi širino kolesarske steze - ta je enaka največji (desni) koordinati x. Nato izpiše številko stolpca, po katerem se bo kolesar pripeljal najdlje in številko vrstice s prvo oviro, na katero bo naletel. V gornjem primeru izpiše 5, 7, ker v 5. stolpcu pride do 7. vrstice. Če je stolpcev, po katerih pride do iste razdalje več, naj izpiše najbolj levega.

Če je MOL kaj spregledal in lahko kolesar morda prevozi kak stolpec, ne da bi naletel na oviro, pa naj program izpiše koordinato stolpca, namesto vrstice z oviro pa napiše "Zmaga!".