DRŽAVNO NATJECANJE 2015. – Drugi dan natjecanja / srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Raspoređivač (engl. scheduler) je dio jezgre operativnog sustava čiji je zadatak da odredi u kojem se trenutku koji proces izvodi na procesoru.

Na raspolaganju imamo računalo s jednim procesorom, a vrijeme od početka rada procesora mjerimo u mikrosekundama.

Svi procesi su periodične prirode, odnosno svaki se treba izvesti određen broj puta.

Točnije, svaki K proces se izvodi na sljedeći način:

• Proces se prvi put pokreće u mikrosekundi Sk (točno Sk mikrosekundi nakon početka rada procesora).
• Proces se izvodi točno Lk mikrosekundi.
• Zatim dolazi pauza od točno Tk mikrosekundi.
• Odmah nakon pauze, proces se opet izvodi Lk mikrosekundi te se postupak ponavlja sve dok se proces ne izvede točno Ck puta.

Dakle proces će se izvoditi točno ukupno Ck Tk mikrosekundi, počet će u mikrosekundi Sk, potpuno završiti Ck Lk + (Ck - 1) * Tk mikrosekundi kasnije, a u tom vremenu bit će Ck - 1 perioda od Tk mikrosekundi u kojima se taj proces ne izvršava i kada se mogu izvršavati drugi procesi.

Raspoređivač je već odredio raspored izvršavanja nekih procesa. Raspored se sastoji od N procesa označenim brojevima od 1 do N , a proces K je opisan parametrima Sk, Tk, Lk, Ck, kao gore.

Raspored je takav da se može izvršiti na procesoru odnosno takav da se u svakom trenutku izvršava točno jedan od procesa (dozvoljeno je da u istoj mikrosekundi jedan proces završi izvođenje, a drugi započne).

Osim N procesa za koje je raspored već fiksiran, na procesoru je potrebno izvršiti M dodatnih procesa. Za svaki novi proces su zadani parametri T, L, C kao gore, a raspoređivač treba za svaki od njih, onim redom kojim su zadani, odrediti najmanje moguće početno vrijeme kako bi se taj proces mogao izvršiti.

Nakon što raspoređivač odredi to najmanje početno vrijeme za prvi novi proces, on se raspoređuje tako da počinje u tom vremenu te se postupak ponavlja za drugi proces, i tako dalje.

Još jednom, početno vrijeme svakog procesa mora biti tako odabrano da se niti jedna dva procesa (uključujući i do sada raspoređene nove procese) ne izvršavaju u isto vrijeme.

Napišite program koji će odrediti početna vremena za sve nove zadane procese.

Rad procesora počinje u nultoj mikrosekundi te je moguće da ta nulta mikrosekunda bude početno vrijeme nekog (već raspoređenog ili novog) procesa.

Ulazni podaci

U prvom redu nalazi se prirodni broj, N (1 ≤ N ≤ 100), - broj već raspoređenih procesa. U svakom od sljedećih N redova nalaze se po četiri cijela broja S, T, L i C (0 ≤ S ≤ 10^12, 1 ≤ T, L ≤ 10^12, 1 ≤ C ≤ 50) koji redom označavaju vrijeme početka izvođenja procesa, vrijeme između dva izvođenja, trajanje jednog izvođenja te broj ponavljanja kao što je opisano u tekstu zadatka.

U sljedećem redu nalazi se prirodni broj, M (1 ≤ M ≤ 10) ) - broj novih procesa koje treba rasporediti. U svakom od sljedećih M redova nalaze se po tri cijela broja T, L i C (1 ≤ T, L ≤ 10^12, 1 ≤ C ≤ 50) koji redom označavaju vrijeme između dva izvođenja, trajanje jednog izvođenja, te broj ponavljanja.

Napomena: Ne mora vrijediti da je već raspoređenim procesima odabrano najmanje moguće početno vrijeme.

Izlazni podaci

Izlaz se treba sastojati od M redova. U K-ti red izlaza potrebno je ispisati jedan nenegativan cijeli broj — najraniji mogući početak izvođenja K-tog novog procesa s ulaza.

Napomena: Preporučamo da za učitavanje, računanje i ispis rezultata koristite 64-bitni cjelobrojni tip podataka (int64 u Pascalu, long long u C/C++).

Primjeri test podataka

Ulaz

2
1 4 3 3
12 6 2 2
3
3 2 2
7 1 3
19 2 2

Izlaz

18
6
4

Ulaz

2
0 1 3 5
15 10 1 2
2
11 1 3
1 2 2

Izlaz

7
20