Županijsko natjecanje 2012. / Osnovna škola (8. razred) - 3. zadatak

U jednoj zemlji more dijeli sjevernu od južne obale. Na svakoj obali nalazi se N gradova, numeriranih od 1 do N, kao na slici (ovdje N=5):

Nekoliko avionskih linija povezuje gradove na južnoj s gradovima na sjevernoj obali.

Avion uvijek polijeće iz grada na južnoj obali i slijeće u grad na sjevernoj.

Iz svakog grada na južnoj obali polazi najviše jedna linija, a u svaki grad na sjevernoj obali dolazi najviše jedna linija.

Za svaku od linija poznato je koje gradove spaja, kada je predviđeno polijetanje aviona, te koliko dugo traje let.

Mirko radi kao kontrolor leta i primijetio je da se putanje nekih aviona sijeku.

Da bi smanjio rizik od sudara, Mirko je odlučio odgoditi polijetanje nekih aviona. On to radi na sljedeći način:

1. avionu A polijetanje je dozvoljeno ako se trenutno u zraku ne nalazi neki drugi avion B čija se linija siječe s linijom aviona A;
2. u protivnom, avion A mora čekati s polijetanjem sve dok se ne spuste svi avioni čija se linija siječe s njegovom, i tek tada može poletjeti;
3. ako Mirko uoči da nekoliko aviona može istovremeno poletjeti (u skladu s pravilima 1. i 2.), on dozvoljava polijetanje onom avionu koji ima najzapadniji polazni grad (grad s najmanjim rednim brojem). Tada Mirko smatra da je i taj avion u zraku, i ponovno primjenjuje ovo pravilo na preostale avione koji su kandidati za polijetanje u tom trenutku (tj. dozvoljava polijetanje sljedećem najzapadnijem avionu čija se linija ne siječe s onima u zraku i tako dalje).

Na gornjoj slici, avion koji polijeće iz grada 4 ne smije biti u zraku u isto vrijeme kada i avion koji polijeće iz grada 3. Bilo koji od ova dva aviona smije biti u zraku zajedno s avionom koji polijeće iz grada 1. Pomozite Mirku da odredi u kojem će trenutku svaki od aviona sletjeti na sjevernu obalu.

ULAZNI PODATCI

prirodan broj N ( 1 ≤ N ≤ 100 ), broj gradova na svakoj obali;

• prirodan broj L ( 1 ≤ L ≤ 100 ), broj linija koje povezuju gradove;

• cijeli brojevi Ji, Si, Pi, Ti (0 ≤ Ji, Si ≤ N, 0 ≤ Pi, Ti ≤ 1000, i = 1, ..., N) koji označavaju redom: polazni grad i-te linije na južnoj obali, ciljni grad i-te linije na sjevernoj obali, predviđeni trenutak polijetanja aviona na i-toj liniji, trajanje leta aviona na i-toj liniji;

• podaci o linijama su navedeni uzlazno sortirani po predviđenom trenutku polijetanja.

IZLAZNI PODATCI

niz cijelih brojeva Di (i=1, …, L) svaki u svom retku.

Broj Di označava trenutak dolaska, odnosno slijetanja aviona na i-toj liniji u njegov ciljni grad na sjevernoj obali.

PRIMJERI TEST PODATAKA

Ulaz

5 4
3 4 1 4
4 2 3 2
1 1 3 7
2 5 4 5

Izlaz

5
12
10
10

Objašnjenje

U trenutku 1 treba poletjeti avion 1 iz grada 3.

Sletjet će u trenutku 5 u grad 4 na sjevernoj obali.

U trenutku 3 treba poletjeti avion 2 iz grada 4, ali njegova se linija siječe s linijom aviona 1, pa on mora čekati.

U trenutku 3 također treba poletjeti avion 3 iz grada 1 - on to smije napraviti jer se njegova linija ne siječe ni sa kim. Sletjet će u trenutku 10 u grad 1 na sjevernoj obali.

U trenutku 4 treba poletjeti avion 4 iz grada 2, ali njegova se linija siječe s linijom aviona 1, pa i on mora čekati.

U trenutku 5 slijeće avion 1, pa bi mogli krenuti avioni 2 i 4.

No njihove se linije također sijeku, pa će krenuti onaj čiji je polazni grad zapadniji - to je avion 4.

On će sletjeti u trenutku 10 u grad na sjevernoj obali. U trenutku 10 slijeću avioni 3 i 4.

Tada može krenuti avion 2.

On će sletjeti u grad 2 na sjevernoj obali u trenutku 12.

Ulaz

4 3
1 3 2 4
3 2 6 2
2 4 10 5

Izlaz

6
8
15

Ulaz

5 5
5 1 5 25
3 5 10 20
2 3 10 40
4 2 15 5
1 4 20 10

Izlaz

30
50
80
85
40

Objašnjenje

U trenutku 5 polijeće avion 1 iz grada 5.

Sletjet će u trenutku 30 u grad 1 na sjevernoj obali.

Linije svih ostalih aviona se sijeku s linijom aviona 1, te moraju čekati dok on ne sleti.

U trenutku 30, avioni 2, 3, 4 i 5 su kandidati za polijetanje.

Najzapadniji od njih je avion 5, pa će on poletjeti iz grada 1 i sletjeti u grad 4 u trenutku 40.

Kada Mirko odobri polijetanje avionu 5, u trenutku 30 s linijom aviona 5 se sijeku linije aviona 3 i 4, pa je jedini preostali (ujedno i najzapadniji) kandidat za polijetanje avion 2.

On dakle polijeće iz grada 3 u trenutku 30 i sletjet će u grad 5 u trenutku 50.

Sada više nema kandidata za polijetanje u trenutku 30.

Avion 3 može poletjeti u trenutku 40 (i stići u trenutku 80).

Avion 4 može poletjeti tek u trenutku 80 (i stići u trenutku 85).