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

U tvrtkama kao što su Facebook i Google, svoje mjesto je zaslužilo i nekoliko naših slavnih natjecatelja koji su, ne tako davno, sjedili u nekoj sličnoj dvorani poput ove te se natjecali za najboljeg programera u Hrvatskoj.

Evo jednog problema s kojim se možda danas susreću i traže za njega neko genijalno rješenje.

Facebook je društvena mreža koja u svakom trenutku sa svih strana svijeta na svoje servere prima velike količine podataka koje treba obraditi.

Jedan takav server svaki podatak preusmjerava na jednu od N radnih stanica koje su spojene na njega.

Stanice su označene brojevima od 1 do N. Server mora odabrati onu stanicu koja je trenutno najmanje opterećena tj. onu na kojoj će taj podatak najprije doći na obradu. Ako je više takvih stanica, odabire se ona s manjom oznakom.

Na žalost, radne stanice se često kvare (zauvijek prestanu raditi).

Kada se to dogodi, svi podaci koji su čekali u redu za obradu na toj stanici se vraćaju na server te ih on opet preusmjerava na već opisan način, istim redom kojim su čekali obradu na stanici.

Ako se neki podatak na stanici obrađivao ili upravo trebao započeti obradu u trenutku kvara, taj podatak se smatra izgubljenim.

Ako za M podataka znamo točno vrijeme kada su došli na server i koliko vremena treba za njihovu obradu, a za K kvarova znamo kada i na kojoj stanici su se dogodili, napiši program koji će odrediti oznaku radne stanicu na koju treba poslati M-ti podatak te vrijeme kada je stanica završila obradu tog podatka.

Vrijeme dolaska podatka na server se iskazuje u sekundama proteklima od početka mjerenja vremena.

Ulazni podaci će biti takvi da se stroj koji počne obrađivati M-ti podatak neće pokvariti.

Napomena: Pretpostavimo da je vrijeme koje server troši na preusmjeravanja zanemarivo, tj. podatak se počinje obrađivati na početku iste sekunde u kojoj je došao na server.

ULAZNI PODATCI

prirodan broj N ( 1 ≤ N ≤ 10 ), broj radnih stanica spojenih na server;

prirodan broj M ( 1 ≤ M ≤ 150 ), broj zadataka koji su stigli na server;

M puta po dva prirodna broja S ( 1 ≤ S ≤ 255 ), sekunda u kojoj je zadatak došao na server te Z ( 1 ≤ Z ≤ 60 ), vrijeme u sekundama potrebno za obradu tog podatka. Vremena S su zadana od manjeg prema većem te su sva različita..

prirodan broj K ( 1 ≤ K ≤ 10 ), broj kvarova;

K puta po dva prirodna broja X ( 1 ≤ X ≤ N ), oznaka stanice koja se pokvarila te Y ( 1 ≤ Y ≤ 255), vrijeme kada se to dogodilo. Vremena Y su zadana od manjeg prema većem te su sva različita.

Napomena: vrijedi da je svako vrijeme Y različito od svakog vremena S.

IZLAZNI PODATCI

prirodan broj koji predstavlja oznaku stanice na koju je server uputio M-ti podatak te vrijeme kada je stanica završila obradu tog podatka od početka mjerenja vremena.

PRIMJERI TEST PODATAKA

Ulaz

3
5
1 5
5 7
6 3
7 4
8 8
0

Izlaz

1
17

Objašnjenje

Zadane su tri stanice i pet podataka.

U 1. sekundi dolazi podatak duljine 5.

Jasno je da će na prvoj stanici najmanje čekati na početak obrade.

U 5. sekundi dolazi podatak duljine 7.

On se usmjerava na drugu stanicu jer bi na prvoj stanici čekao jednu sekundu početak obrade.

U . 6. sekundi dolazi podatak duljine 3. On se usmjerava na prvu stanicu koja je trenutno slobodna.

U 7. sekundi dolazi podatak duljine 4. Na prvoj stanici bi čekao 2 a na drugoj 6 sekundi na početak obrade.

Zato ga usmjeravamo na treću stanicu.

U 8. sekundi dolazi podatak duljine 8.

Njega upućujemo na prvu stanicu gdje će 1 sekundu čekati na početak obrade što s njegovih osam i trenutnim vremenom čini 17 kao završno rješenje.

Ulaz

3
5
5 30
10 50
20 40
40 30
41 20
0

Izlaz

2
80

Objašnjenje

U sekundi 5 dolazi podatak duljine 30.

On se odmah počne obrađivati na stanici 1.

Završit će u trenu 35. U sekundi 10 dolazi podatak duljine 50.

On se odmah počne obrađivati na stanici 2.

Završit će u trenu 60. U sekundi 20 dolazi podatak duljine 40.

On se odmah počne obrađivati na stanici 3. Završit će u trenu 60.

U sekundi 40 dolazi zadatak duljine 30.

Stroj 1 je slobodan, pa se on odmah počne obrađivati na stanici 1.

Završit će u trenu 70. U sekundi 41 dolazi podatak duljine 20.

On će se početi izvršavati u trenu 60 na stanici 2.

Završit će u trenu 80.

Ulaz

3
5
10 50
20 30
25 45
30 30
40 5
1
2 35

Izlaz

3
75