Državno natjecanje 2012. godine za 1. i 2. razred Srednje Škole - 4. zadatak

Državno natjecanje 2012. godine za 3. i 4. razred Srednje Škole - 4. zadatak

Preko sedam brda, preko sedam mora, jako blizu izlazećeg Sunca u područja potresa, cunamija i nindža ratnika postoji jedna zemlja. U toj zemlji ljudi vole preciznost i točnost. Posebno su ponosni na svoje vlakove koji navodno godišnje kasne manje od vremena potrebnog za brut rješenje ovog zadatka! Promotrimo ovdje jednu situaciju s kojom se svaki dan susreću japanski željezničari.

Zadana je jedna pruga duljine L metara. Na toj pruzi postoji S željezničkih postaja (postavljenih na cjelobrojne točke na pruzi) koje prugu dijele na S-1 segmenata. Dvije postaje od njih S se nalaze na krajevima pruge i to početna postaja u točki X=0 i završna u točki X=L.

Na pruzi se u početnom trenutku promatranja nalazi V vlakova. Vlakovi su nalaze na otvorenoj pruzi (tj. nisu u stanici), u svakom segmentu se nalazi maksimalno jedan vlak i svi ti vlakovi se kreću prema zadnjoj stanici na poziciji X=L. Vlakovi se po pruzi stalno kreću (osim kada stoje u stanici), a brzina svakog vlaka je konstantna i iznosi jedan metar u sekundi.

Glavni prometnik na toj pruzi iz kontrolne sobe ima potpuni nadzor i kontrolu nad njom. Zbog sigurnosti, unutar jednog segmenta (koji ne obuhvaća stanice) se smije nalaziti samo jedan vlak dok je u stanicama njihov broj neograničen. To znači da prometnik ne smije pustiti vlak iz stanice u naredni segment sve dok taj segment nije slobodan. Kada može, prometnik vlakove iz postaje pušta dalje onim redoslijedom kako su u postaju i ulazili.

Napiši program koji će za zadanu početnu situaciju na pruzi za svaki vlak ispisati vrijeme potrebno da taj vlak od trenutne pozicije dođe do zadnje stanice!

ULAZNI PODACI

• prirodan broj L ( 1 ≤ L ≤ 10000000 ), duljina pruge u metrima;
• prirodan broj S ( 2 ≤ S ≤ 2000 ), broj postaja na promatranoj pruzi;
• prirodan broj V ( 1 ≤ V ≤ 2000 ), broj vlakova na promatranoj pruzi;
• strogo rastući niz od S nenegativnih cijelih brojeva Si ( 0 ≤ Si ≤ L, i=1..S, S1=0 i Ss=L ), gdje je Si pozicija i-te postaje na pruzi;
• strogo rastući niz od V prirodnih brojeva Vi ( 1 ≤ Vi ≤ L-1, i=1..V, pri čemu vrijedi da Vi≠Sj za svaki i=1..V i j=1..S), gdje je Vi pozicija vlaka s oznakom „i“ na pruzi;

IZLAZNI PODACI

u V redaka izlaza treba ispisati po jedan prirodan broj, vrijeme u sekundama potrebno da vlak s oznakom “i” (i=1..V) dođe do završne stanice.

Napomena: U 50% test primjera vrijedit će da je L ≤ 2000 te S ≤ 100 i V ≤ 100.

PRIMJERI TEST PODATAKA

ulaz

8 3 2
0 3 8
2 4

izlaz

9
4

ulaz

13 4 3
0 4 6 13
3 5 7

izlaz

20
13
6

ulaz

100 5 4
0 25 50 75 100
1 30 70 80

izlaz

99
70
45
20