ACM RTK - 1. skupina

Kino

Mirko rad hodi v kino (običajnega, z eno samo dvorano), kjer vrtijo filme brez prekinitev enega za drugim. Domov bo šel z avtobusom, vendar pa sovraži stati na postaji in čakati na avtobus. Po vsakem filmu se odloča, ali naj gre na avtobus ali naj pogleda še en film. Pred seboj ima dva seznama:

• vozni red avtobusov: npr. [(0,40),(1,50),(2,30),(3,30),(4,30),(5,35),(6,5)]; to so pari (ure, minute), ki povedo, kdaj odpeljejo avtobusi s postaje pred kinom; pri tem se čas meri od nekega izbranega začetnega trenutka, zato lahko število ur sčasoma tudi preseže 24;
• seznam trajanj filmov, ki jih vrtijo v kinu: na primer [(1, 30), (2, 10), (1, 40), (0, 50)], torej spet v obliki parov (ure, minute).

Prvi film se začne ob trenutku (0,0). Med filmi ni prekinitve. Mirko pogleda vedno vsaj prvi film. Vhodni podatki so taki, da zagotovo lahko dobi avtobus za domov, če pogleda samo prvi film. Rad bi minimiziral čas čakanja na postaji (to med drugim tudi pomeni, da seveda noče ostati v kinu tako dolgo, da bi zamudil še zadnji avtobus). Opiši postopek, ki izračuna, koliko filmov naj pogleda. Mirko lahko pride od kina do avtobusne postaje v trenutku, tako da lahko ujame avtobus tudi, če le-ta odpelje ob istem času, ob katerem se konča zadnji film, ki si ga je ogledal.

Pri zgornjem primeru se na primer izkaže, da je najbolje, če pogleda tri filme. V tem primeru mora čakati na avtobus 15 minut; če bi pogledal en film, bi moral čakati 20 minut, po drugem filmu bi moral čakati kar 50 minut, po četrtem filmu pa bi celo zamudil zadnji avtobus (in to za 5 minut).