Županijsko natjecanje 2012. godine za 1. i 2. razred Srednje Škole - 2. zadatak

Ivica je zastupnik u Parlamentu. On i njegove kolege zastupnici svaki dan dolaze na posao. Za svakog zastupnika poznato je kad dolazi u parlament te koliko dugo tamo ostaje. Svakog dana svi zastupnici napuste parlament prije ponodi. Ivica je saznao da de sutra televizija prenositi zasjedanje. Televizijski de prijenos trajati T minuta, a on smije birati vrijeme početka te minute u kojima de se puštati reklame. Ukupno trajanje reklama može biti do maksimalno R minuta, ali se ne smiju pustiti u prvoj i u zadnjoj minuti TV prijenosa. Ivica želi odabrati takvo vrijeme početka prijenosa i takav raspored reklama da se ni u jednom trenutku ne može vidjeti manje od Z prisutnih zastupnika. Ako postoji više takvih rasporeda, Ivica bira onog s najmanjim ukupnim trajanjem reklama. Ako i dalje postoji više takvih rasporeda, Ivica bira najranije vrijeme početka prijenosa. Napišite program koji de pomodi Ivici!

ULAZNI PODACI

Ivica de upisati: N, T, R, Z Zatim N puta: H, M i O

N – broj zastupnika u parlamentu (1 ≤ N ≤ 200)

T – trajanje televizijskog prijenosa, u minutama (1 ≤ T ≤ 500)

R – najdulje dozvoljeno ukupno trajanje reklama, u minutama (0 ≤ R ≤ T-2)

Z – najmanji broj zastupnika koje želimo u svakom trenutku vidjeti na televiziji (1 ≤ Z ≤ N)

H i M – vrijeme dolaska n-tog zastupnika, sat i minuta (0 ≤ H ≤ 23, 0 ≤ M ≤ 59 )

O – vrijeme zadržavanja n-tog zastupnika u parlamentu, u minutama (1 ≤ O ≤ 500)

Napomena: Ulazni podaci bit de takvi da de rješenje uvijek postojati.

IZLAZNI PODACI

Vaš program treba ispisati dva cijela broja odvojena razmakom koji opisuju odabrano vrijeme početka televizijskog prijenosa. Prvi broj je sat početka prijenosa (0-23), a drugi broj je minuta početka prijenosa (0-59).

PRIMJERI TEST PODATAKA

ulaz

1 60 2 1
10 30 100

izlaz

10 30

ulaz

3 100 10 2
8 15 200
9 12 190
9 20 70

izlaz

9 12

ulaz

3 30 15 2
8 50 10
8 55 90
9 10 15

izlaz

8 55

Objašnjenje

Pojašnjenje trećeg test primjera: Kako nije mogude imati 2 zastupnika u parlamentu tijekom 30 minuta, prijenos počinje točno u 8 sati i 55 minuta. Nakon pet minuta prvi zastupnik odlazi iz parlamenta pa puštamo 10 minuta reklama dok ne dođe tredi zastupnik.