Državna razina / Primjena algoritama OŠ 2021. / Osnovna škola (7. razred) - 3. zadatak

Gabrijel se zaposlio kao regulator željezničkog prometa. Svaki dan mora napraviti vozni red vlakova na pruzi koja se proteže uz Dravu.

Pruga je jednokolosječna, što znači da ne mogu u isto vrijeme prolaziti vlakovi u oba smjera. Uz prugu se nalazi N postaja sa oznakama od 1 do N.

Prugu još možemo zamisliti kao dužinu s N točaka, gdje točke predstavljaju postaje. Gabrijel čim dođe na posao dobije popis od M vlakova koji će taj dan prevoziti putnike.

Vlakovi su dani u kronološkom poretku vremena njihovog polaska. Također, za svaki vlak je poznata njegova početna i završna postaja.

Vlak se ne zaustavlja na niti jednoj postaji osim početne i završne, a kada dođe na završnu postaju odmah se uklanja s pruge.

Poznato je da svi vlakovi voze istom brzinom te da im je za put između dvije uzastopne postaje potrebno 5 minuta.

Gabrijel mora osigurati da ne dođe do sudara te da se vlakovi koji završe vožnju stignu ukloniti s pruge. S ciljem ispunjenja povjerene mu zadaće, osmislio je sljedeća pravila:

• niti jedan vlak ne smije krenuti prije nekog drugog vlaka koji je prije njega na popisu, ali smije krenuti istovremeno;
• nakon što vlak krene iz, prođe pokraj ili se zaustavi u nekoj postaji, pokraj te postaje idući vlak smije proći, krenuti ili se zaustaviti tek nakon 5 minuta;
• dva se različita vlaka ne smiju istovremeno nalaziti između dvije uzastopne postaje.

Gabrijel ide redom po popisu vlakova i odabire najranije moguće vrijeme polaska vlaka tako da ne prekrši zadana pravila među vlakovima čije je vrijeme polaska već odabrao u tom trenutku.

Pomozi Gabrijelu i ispiši kada će svaki vlak krenuti ako je poznato da prvi vlak uvijek kreće u 8:00. Svi vlakovi će krenuti prije ponoći.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi N i M (1 ≤ N, M ≤ 50), brojevi iz teksta zadatka.

U sljedećih M redaka nalaze se po dva prirodna broja, koji redom predstavljaju oznake početne i završne postaje vlakova za i-ti vlak. Početna i završna postaja su međusobno različite.

Izlazni podaci

Za svaki vlak u zaseban redak ispiši njegovo vrijeme polaska. Vremena ispiši u obliku: xx:xx.

Primjer zadatka

Ulaz

5 3
1 2
1 5
3 2

Izlaz

08:00
08:05
08:20

Objašnjenje

Opis prvog probnog primjera: Prvi vlak može krenuti u 08:00. Drugi vlak mora pričekati 5 minuta jer kreće iz iste postaje kao prvi vlak.

Treći vlak ne smije krenuti u 08:05 jer bi se tada istovremeno s prvim vlakom nalazio između postaja 2 i 3, ne smije krenuti u 08:10 jer bi se tada nalazio između postaja s oznakama 2 i 3 istovremeno kad i drugi vlak.

Ne može krenuti niti u 08:15 jer u to vrijeme drugi vlak prolazi pokraj postaje s oznakom 3 koja je ujedno i početna postaja trećeg vlaka. Napokon u 08:20 vlak treći može krenuti.

Ulaz

10 2
7 8
10 1

Izlaz

08:00
08:00

Objašnjenje

Opis drugog probnog primjera: Drugi vlak smije krenuti istovremeno kao prvi jer će u prvi vlak u 08:05

završiti vožnju, a drugi vlak će do postaje s oznakom 8 doći tek u 08:10.

Ulaz

5 4
2 3
3 2
1 4
5 2

Izlaz

08:00
08:10
08:15
08:30