Programozás‎ > ‎Feladatok‎ > ‎

Vasúti menetrend

Egy vasúti vonalon két megálló van: A és B. A vonatok A-ból B-be vagy B-ből A-ba közlekednek, egy nap többször is. Amikor egy vonat B-be érkezik A-ból (vagy A-ba B-ből), bizonyos ideig várnia kell, mielőtt újra elindulhat - ezt a kötelező várakozási időt megfordulási időnek hívjuk. Például ha a vonat 12:00-kor érkezik meg, és 0 perc a megfordulási ideje, akkor 12:00-kor rögtön indulhat is vissza.

A vasúti menetrend megadja az indulási és érkezési időket az A és B állomásokra. A járatokat üzemeltető társaság szeretné tudni, hogy az adott menetrend megvalósításához legkevesebb hány vonat kell az A és B állomásra. A feltétel az, hogy ha a menetrend szerint indulni kell egy vonatnak, akkor az  adott állomáson legyen legalább egy indulásra kész vonat. Feltesszük, hogy elég sok vágány van az állomásokon, tehát a vonatok sorrendje változhat a nap során. Csak menetrend szerinti vonatok közlekedhetnek A és B között.

Feladat

Írjunk programot, ami megadja, hogy A-ban illetve B-ben legalább hány vonatnak kell lennie a nap elején, hogy a menetrend fennakadás nélkül működjön.

Bemenet

Az első sor a tesztesetek N száma, ezután N teszteset következik.

Minden teszteset a visszafordulási idővel kezdődik (T), ez percekben van megadva. A következő sor az A-ból és B-ből induló menetrend szerinti járatok számát tratlmazza: NA és NB. NA sorban ezután az A-ból, majd NB sorban a B-ből induló járatok indulási és érkezési ideje következik.

Az indulási és érkezési idők formátuma ÓÓ:PP, 00:00-tól 23:59-ig, mindig két jegyre formázva (pl. 07:00). Az indulási idő mindig kisebb mint az érkezési. A járatok tetszőleges sorrendben követhetik egymást a bemenetben.

Méretek

1 <= N <= 100

Kis bemenet

0 <= NA, NB <= 20

0 <= T <= 5

Nagy bemenet

0 <= NA, NB <= 100

0 <= T <= 60


Kimenet

A kimenet minden sora egy-egy teszteset megoldása: az a-ba és B-be minimálisan szükséges vonatok száma, a példának megfelelő formátumban.

Példa

Bemenet  Kimenet
2
5
3 2
09:00 12:00
10:00 13:00
11:00 12:30
12:02 15:00
09:00 10:30
2
2 0
09:00 09:01
12:00 12:02
Case #1: 2 2
Case #2: 2 0


Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2008 Qualification Round
Algoritmusok: kupac adatszerkezet, mohó algoritmus