Fişierul intrare/ieşire:prieteni.in, prieteni.outSursăONI 2006, clasa 10
AutorRoxana TamplaruAdăugată demarcelcodreaCodrea Marcel marcelcodrea
Timp execuţie pe test0.2 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/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.inprieteni.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content