시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 5 | 1 | 1 | 20.000% |
Studenti nekog fakulteta su, zbog razmirica s dekanom, odlučili organizirati blokadu prostora fakulteta. To znači da odredeni broj studenata mora biti fizički prisutan na fakultetu tijekom 24 sata. Organizatoribi medu sobom željeli podijeliti dežurstva na blokadi što je moguće poštenije, pa su osmislili slijedećapravila:
Napišite program koji će omogućiti organizatorima blokade da utvrde koliki je maksimalan broj studenata M takav da je moguće napraviti raspored koji zadovoljava gornja ograničenja, a da u svakom trenutku dana (od ponoći do ponoći) dežura barem M studenata.
Možete pretpostaviti da je zamjena studenata koji dežuraju trenutna, tj. da ako dvoje studenta napuste blokadu a zamijene ih drugo dvoje, možete smatrati da je tijekom smjene dežurstva na blokadi cijelo vrijeme bilo dvoje studenata.
U prvom redu nalazi se cijeli broj n (1 ≤ n ≤ 50), broj studenata koji žele sudjelovati u blokadi. Nakon toga slijedi n blokova gdje svaki blok opisuje želje i mogućnosti jednog studenta.
Svaki blok počinje s dva broja, ki (1 ≤ k ≤ 50) i mi (1 ≤ mi ≤ 1440), redom broj vremenskih perioda u kojima je i-ti student slobodan od drugih obaveza i može sudjelovati u blokadi te najveći ukupni broj minuta koje je spreman posvetiti dežuranju u jednom danu.
U preostalih ki redova u bloku, nalaze se vremenski trenunci poˇcetka i kraja uzastopnog perioda kada je student slobodan, odvojeni razmakom. Periodi se mogu preklapati, a njihova unija predstavlja vrijeme kada student može biti prisutan na blokadi.
Vremenski su trenuci formatirani kao “HH:MM” (00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59). Ponoć je predstavljena s “00:00”. Kada je kraj prije početka, to znači da student može ostati na blokadi i preko ponoći. Na primjer, period “23:00 03:00” znači da student može biti prisutan od 23 sata do idućeg jutra u 3. Ako su početak i kraj jednaki, to znači da student može biti svih 24 sata na blokadi.
Potrebno je ispisati jedan cijeli broj – traženi najveći broj studenata M koji može biti u svakom trenutku na blokadi, uz ranije opisane pretpostavke.
3 1 540 00:00 00:00 3 480 08:00 10:00 09:00 12:00 13:00 19:00 1 420 17:00 00:00
1
5 1 720 18:00 12:00 1 1080 00:00 23:00 1 1080 00:00 20:00 1 1050 06:00 00:00 1 360 18:00 00:00
2
3 1 1440 00:00 00:00 1 720 00:00 12:15 1 720 12:05 00:15
1