furnici
Una dintre cele mai importante functii din colonia de furnici este cea de ofiter de circulatie. Motivul este ca in musuroiul de furnici exista un tunel foarte ingust, astfel incat prin tunel nu pot sa treaca doua furnici una pe langa alta. Din fericire, in tunel exista niste locuri speciale, unde furnicile pot sta si pot astepta pana trec alte furnici. Furnicile pot trece una pe langa alta fara nici o problema la capetele tunelului.
Ofiterul de circulatie cunoaste lungimea tunelului, precum si pozitiile locurilor speciale, in care furnicile pot stationa. In fiecare dimineata ofiterul de serviciu primeste o lista cu toate sosirile in tunel. Misiunea sa este de a organiza traficul astfel incat toate furnicile sa poata traversa tunelul. Bineinteles ca acest lucru poate fi realizat in multe moduri, mai rapid sau mai lent. Deoarece atunci cand ultima furnica va iesi din tunel, ofiterul de serviciu isi poate incheia programul, interesul sau este de a organiza traficul astfel incat acest lucru sa se intample cat mai repede.
Orice furnica se deplaseaza cu 1cm/s. In locurile speciale pot astepta oricate furnici, iar dimensiunile unui astfel de loc pot fi neglijate (poate fi considerat punctiform).
Cerinta
Scrieti un program care sa determine timpul minim necesar pentru ca toate furnicile sa traverseze tunelul.
Date de intrare
Fisierul de intrare furnici.in contine pe prima linie doua numere naturale D si U, separate printr-un spatiu; D reprezinta lungimea tunelului exprimata in cm, iar U reprezinta numarul de locuri speciale din tunel. Fiecare dintre urmatoarele U linii contine pozitia unui loc special din tunel; pozitia este precizata prin distanta fata de capatul din stanga al tunelului (exprimata in cm); pozitiile sunt date in ordine de la stanga la dreapta. Pe urmatoarea linie se afla un numar natural L, care reprezinta numarul de furnici care intra prin capatul din stanga al tunelului. Fiecare dintre urmatoarele L linii contine timpul de sosire a unei furnici la capatul din stanga al tunelului. Pe urmatoarea linie se afla un numar natural R, care reprezinta numarul de furnici care intra prin capatul din dreapta al tunelului. Fiecare dintre urmatoarele R linii contine timpul de sosire a unei furnici la capatul din dreapta al tunelului.
Date de iesire
Fisierul de iesire furnici.out contine o singura linie pe care se afla timpul minim necesar pentru ca toate furnicile sa traverseze tunelul, exprimat in secunde.
Restrictii
1 <= D <= 1000000
(un milion)
1 <= U,
L, R <= 100000
(o suta de mii)
D > U
Timpii de
sosire sunt exprimati in secunde si sunt numere naturale <= 2000000
(doua milioane)
Exemple
|
furnici.in |
furnici.out | furnici.in | furnici.out | furnici.in |
furnici.out |
|
5 1 2 1 3 1 2 |
8 |
10 1 3 1 0 1 2 |
16 |
10 2 4 6 2 0 4 1 0 |
14 |
Timp maxim de executie/test: 0.2 secunde.
prof. Serban
Marinel
Liceul de Informatica "Gr. C. Moisil" Iasi
Contact: marinel_serban at yahoo.com