| Fişierul intrare/ieşire: | prieteni.in, prieteni.out | Sursă | ONI 2006, clasa 10 |
| Autor | Roxana Tamplaru | Adăugată de |  Codrea Marcel •marcelcodrea |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Prieteni
Mai multi prieteni iubitori ai muntelui au parte de o adevarata aventura, intr-una din zilele vacantei de iarna. Surprinsi de dificultatea traseului ales spre parcurgere si de inrautatirea rapida a conditiilor meteo (ninsoare si viscol) isi dau seama, odata cu lasarea intunericului, ca ar fi mai bine sa se adaposteasca pe timpul noptii, urmand sa revina la cabana in dimineata zilei urmatoare. Norocul pare sa le surada in cele din urma. Pe partea cealalta a prapastiei la marginea careia se afla, se zareste un refugiu. Cercetand imprejurimile, descopera un podet din lemn care i-ar putea ajuta sa traverseze prapastia. Dupa o evaluare mai atenta, realizeaza ca traversarea nu va fi deloc usoara, pentru ca exista cateva traverse lipsa, iar starea podetului permite traversarea sa de catre cel mult 2 persoane, la un moment dat. Vizibilitatea este extrem de redusa si mai exista o singura lanterna functionala ce va trebui folosita judicios pentru traversarea in siguranta a tuturor membrilor grupului. Traversarea se va face alternativ in ambele sensuri, pentru a putea readuce lanterna celor care n-au traversat inca.
Cunoscand numarul membrilor grupului, timpul fiecaruia de traversare (exprimat in secunde) si stiind ca, la o traversare in care sunt angajati doi membri, timpul este dat de timpul de traversare al celui mai lent dintre ei, gasiti o strategie adecvata pentru ca toti membrii grupului sa traverseze prapastia in timpul cel mai scurt. Daca exista mai multe solutii cu acelasi timp minim de traversare, se va determina numai una, oricare dintre ele.
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.
Date de iesire
Solutia se va scrie in fisierul prieteni.out. Pe primele linii se va descrie strategia urmata pentru atingerea acestui timp minim: fiecare linie i va contine una sau doua valori, indicand persoana sau persoanele ce traverseaza podetul la pasul i. Fiecare persoana este indicata chiar prin timpul sau de traversare, specificat corespunzator in fisierul cu datele de intrare prieteni.in.
Pe ultima linie se va scrie valoarea ce reprezinta timpul minim total (exprimat in secunde) necesar pentru ca toti cei n membri ai grupului sa traverseze prapastia.
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.
Exemplu
| prieteni.in | prieteni.out |
|---|---|
| 3 2 3 5 | 2 3 2 2 5 10 |
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.
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.
