Državno natjecanje 2019. / Osnovna škola (8. razred) - 2. zadatak

U Primoštenu se zbog velike potražnje za šišanjem tijekom državnog natjecanja iz informatike otvorio frizerski salon Sretno.

Vlasnik je odlučio zaposliti N frizera, označenih brojevima od 1 do N.

Svaki od frizera ima zadanu razinu perfekcionizma Pi.

Jučer se u salonu ošišalo M mušterija. Svaka mušterija je u različito i poznato vrijeme Vi ušla u salon.

Salon se otvorio u 08:00, a zatvorio tek nakon što je svih M mušterija završilo sa šišanjem. Sve su mušterije završile sa šišanjem prije ponoći.

Svaka mušterija ima određenu razinu zahtjevnosti frizure Zi. Poznato je da frizer s razinom perfekcionizma P šiša mušteriju sa zahtjevnošću frizure Z točno P * Z minuta.

Kada neka mušterija uđe u salon, ona stane na kraj reda čekanja.

Kad god postoji neki frizer koji nikoga ne šiša, prva mušterija u redu mora odlučiti hoće li sačekati nekog određenog frizera, ili će sjesti na šišanje kod nekog frizera koji nikoga trenutno ne šiša i kojeg nitko već ne čeka.

Ta odluka je konačna i mušterija tada izlazi iz reda čekanja.

Ako se više mušterija opredijelilo na čekanje istog frizera, frizer će ih šišati onim redom kojim su se i opredjeljivale za njega.

Sve mušterije jako cijene svoje vrijeme te će svaka od njih uvijek donijeti onu odluku koja bi joj zajamčila da u salonu provede što manje vremena.

Ako neka mušterija može donijeti više takvih odluka, odabrat će onu nakon koje će se šišati kod frizera s najmanjom oznakom.

Za svaku od M mušterija ispiši u koje je vrijeme završila sa šišanjem.

Napomena: sve radnje, osim šišanja i čekanja, događaju se u zanemarivom vremenu.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100), broj frizera.

U sljedećem retku nalazi se N prirodnih brojeva Pi (1 ≤ Pi ≤ 200), razine perfekcionizma frizera, redom od frizera s oznakom 1 do frizera s oznakom N.

U drugom retku nalazi se prirodan broj M (1 ≤ M ≤ 100), broj mušterija.

U sljedećih M redaka nalaze se podaci o svakoj od mušterija: po jedan prirodan broj Zi (1 ≤ Zi ≤ 200), zahtjevnost frizure odvojena razmakom od vremena dolaska Vi (08:00 ≤ Vi) u obliku SS:MM.

Mušterije su zadane redom kojim su dolazile u salon.

IZLAZNI PODATCI

Ispiši M redaka, trenutak u kojem je svaka od mušterija završila sa šišanjem, redom kojim su mušterije dane u ulazu.

PRIMJERI TEST PODATAKA

Ulaz

1
2
4
5 08:00
10 08:01
15 08:02
20 09:00

Izlaz

08:10
08:30
09:00
09:40

Objašnjenje

Opis prvog primjera: Prva će mušterija u 08:00 doći u salon i odmah započeti sa šišanjem kod jedinog frizera. Druga će mušterija u 08:01 doći u salon i stati u red čekanja, a treća će u red čekanja stati u 08:02.

U 08:10 će prva mušterija završiti sa šišanjem, a druga će započeti svoje šišanje. U 08:30 će druga mušterija završiti sa šišanjem, a treća će započeti svoje šišanje.

U 09:00 će treća mušterija završiti sa šišanjem, a četvrta će doći u salon, stati u red čekanja i odmah započeti svoje šišanje, s kojim će završiti u 09:40.

Ulaz

3
3 4 5
5
4 11:00
2 11:04
1 11:06
3 11:07
4 11:08

Izlaz

11:12
11:12
11:11
11:21
11:28

Objašnjenje

Opis drugog primjera: Prva će mušterija u 11:00 započeti sa šišanjem kod prvog frizera.

Druga će mušterija u 11:04 započeti sa šišanjem kod drugog frizera, a treća u 11:06 kod trećeg frizera.

Četvrta će mušterija doći u 11:07 i stati u red čekanja. Peta će doći u 11:08 i stati u red čekanja.

Treća će mušterija u 11:11 završiti sa šišanjem te će tada treći frizer biti slobodan pa će četvrta mušterija koja je prva u redu čekanja morati donijeti odluku. Ona će, kako bi uštedjela vrijeme, odlučiti ne sjesti na šišanje kod trećeg frizera odmah, već čekati prvog frizera pa se šišati kod njega.

Nakon donošenja odluke, ona izlazi iz reda čekanja. Tada će treći frizer i dalje biti slobodan pa će peta mušterija, kao prva u redu čekanja, donijeti odluku da će sačekati drugog frizera.

U 11:12 istovremeno će prva i druga mušterija završiti sa šišanjem, dok će četvrta i peta mušterija započeti šišanje, četvrta kod prvog, a peta kod drugog frizera.

Ulaz

2
10 10
4
3 20:57
4 20:58
5 20:59
1 21:00

Izlaz

21:27
21:38
22:17
21:48