Problema prod3, Campion 2009
.campion, algoritmica, informatica, OJI, ONI, Probleme algoritmica, prod3
Să considerăm x o secvenţă de N numere întregi.
Cerinţă
Scrieţi un program care să determine 3 numere din secvenţa x, numere al căror produs să fie maxim.
Date de intrare
Fişierul de intrare prod3.in conţine pe prima linie numărul natural N. Pe cea de a doua linie se află cele N numere întregi din secvenţa x, separate prin spaţii.
Date de ieşire
Fişierul de ieşire prod3.out va conţine o singură linie pe care vor fi scrise cele 3 numere din secvenţă al căror produs este maxim, separate prin spaţii.
Restricţii
- 3 ≤ N ≤ 100 000
- Numerele din secvenţă sunt din intervalul [-30000,30000].
- Dacă există mai multe soluţii, afişaţi oricare dintre acestea.
Exemple
| prod3.in | prod3.out | prod3.in | prod3.out |
| 9
3 5 1 7 9 0 9 -3 10 |
9 10 9 | 4 -3 0 -5 -7 |
0 -3 -5 |
Solutie
Exista cateva variante ce ne pot duce la solutia maxima.Prima ar fi ca toate numerele sa fie mai mari ca 0.Asta inseamna ca solutia va fi max1,max2,max3 > 0.Acest lucru duce la o solutie adevarata doar daca avem numere pozitive.Din pacate,problema ne spune ca intervalul contine numere negative.Pentru asta trebuie sa avem in vedere si min1,min2 cele mai mici valori din interval.
Solutia finala va fi data astfel :
daca max1>0 si min1*min2>max2*max3 atunci solutia este max1,min1,min2
altfel solutia este max1,max2,max3
Descarca solutia la problema prod3 propusa la Campion 2009,Runda 4
Recomandam, pe aceeasi tema
Despre autorul articolului :
Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.
Nou pe 
Nou pe 
