The city of Ljubljana is known for its extreme care for cyclying safety. To this end, it puts "give way" signs and various obstacles on cycling paths, eliminates cycling paths that are potentially dangerous (and would, in the city officials' opinion better be used for new parking lots), adds curbs to slow down cyclists and so forth. One of such projects can be visible just in front of our faculty: the city realised that drivers crossing the cycling path (which is one of the few nice cycling paths in Ljubljana) may not know that they have to yield to cyclists, so the city has put "yield" sign on the cycling path. They also added some obstacles that cyclist must drive around in order to slow them down. (More here.)

Warm-up task

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

(Do not submit this part. It's just for warming up.)

A new approach to ensuring cycling safety could be to add cube-like obstacles. Write a program that starts with a list of obstacles, named ovire, which contains a list of obstacle coordinates. This should be followed by variable x containing the x-coordinate (column) where the cyclist will ride. The program must print the y coordinate of the top-most obstacle in that column.

Program may thus start with

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

This represents the obstacles in the figure. With this data, it prints 6 because this is the y-coordinate of the first obstacle in column 3. The program must of course also work for other arrangements of obstacles, arbitrary width of the path and any coordinate x. To test that it works, try different value of x.

Mandatory task

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

(This is the part that you must submit.)

Obstacles are in fact not cubes but blocks like those you can see in front of FRI or in the above blog. Their positions are thus given as triplets (x1, x2, y), where x1 and x2 (x1 <= x2) are column numbers where the obstacle begins and ends.

Write a program that starts with a list of obstacles, for instance

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

(this corresponds to the figure) and outputs the number of the line where the cyclist will encounter the first obstacle. In the above case, it prints 5. It must, of course, also work for different data.

You can assume that the cyclist will always encounter an obstacle; there are no obstacle-free columns.

Extra task

Add this to the above program: the program should first discover the width of the path - it equals the largest coordinate x2. Then it outputs the number of the column that will let the cyclist drive the furthest, that is, the one at which the first obstacle appears at the lowest line. In the above case, it prints 5, 7, because riding in the 5th column lets him go to the 7th line. In case of ties, print the number of the left-most column.

If the city missed some column and it can be passed without encountering an obstacle, the program should print the number of that column and "Zmaga!" (win!).