prieteni

Prieteni

h2. Date de intrare

Datele de intrare se preiau din fisierul $prieteni.in$. Acesta contine pe prima linie valoarea $n$, adica numarul prietenilor, iar pe urmatoarele $n$ linii cate un numar pe linie, numarul $ti$ aflat pe linia $i$+1 din  fisier, reprezentand timpul (exprimat in secunde) in care persoana $i$ din grup poate traversa singura podetul.

Datele de intrare se preiau din fisierul $prieteni.in$. Acesta contine pe prima linie valoarea $n$, adica numarul prietenilor, iar pe urmatoarele $n$ linii cate un numar pe linie, numarul $T{~i~}$ aflat pe linia $i$+1 din fisier, reprezentand timpul (exprimat in secunde) in care persoana $i$ din grup poate traversa singura podetul.

h2. Date de iesire

h2. Restrictii si observatii
* $1 ≤ n ≤ 1000$

* $1 ≤ ti ≤ 3000$
* in orice moment pot traversa podetul cel mult 2 membri ai grupului
* pot exista mai multe persoane cu acelasi timp de traversare, dar in specificarea solutiei nu are importanta carei persoane ii apartine timpul respectiv.

* $1 ≤ T{~i~} ≤ 3000$
* In orice moment pot traversa podetul cel mult 2 membri ai grupului.
* Pot exista mai multe persoane cu acelasi timp de traversare, dar in specificarea solutiei nu are importanta carei persoane ii apartine timpul respectiv.

h3. Explicatie

* Mai intai traverseaza persoanele $1$ si $2$, avand timpii $2$, respectiv $3$ secunde. Timpul de traversare la aceasta trecere este dat de timpul cel mai mare: $3$ secunde. Se intoarce apoi persoana $1$ cu lanterna, timpul de traversare fiind de $2$ secunde. La a treia traversare, trec persoanele $1$ si $3$, avand timpii $2$, respectiv $5$ secunde. De data aceasta, timpul de traversare la aceasta trecere este dat de timpul cel mai mare: $5$ secunde. Timp total: $3+2+5=10$ secunde.

Mai intai traverseaza persoanele $1$ si $2$, avand timpii $2$, respectiv $3$ secunde. Timpul de traversare la aceasta trecere este dat de timpul cel mai mare: $3$ secunde. Se intoarce apoi persoana $1$ cu lanterna, timpul de traversare fiind de $2$ secunde. La a treia traversare, trec persoanele $1$ si $3$, avand timpii $2$, respectiv $5$ secunde. De data aceasta, timpul de traversare la aceasta trecere este dat de timpul cel mai mare: $5$ secunde. Timp total: $3+2+5=10$ secunde.

Aceasta este una dintre strategiile posibile. O alta solutie corecta: traverseaza mai intai persoana $1$ cu persoana $3$, se intoarce persoana $1$ si traverseaza apoi persoana $1$ cu persoana $2$, si in acest caz se obtine acelasi timp minim de $10$ secunde.
== include(page="template/taskfooter" task_id="prieteni") ==

1877