BitCell

Salutare!!!

Dacă vă simțiți în formă, puteți să îmi dați niște indicații la problema expresie de pe campion.edu.ro ?

Nu trebuie să determinați voi ce trebuie să fac in problemă.

Se citește un număr natural n și n numere.
Trebuie să pun între cele n numere 2 operații de înmulțire, și logic N-3 operații de adunare astfel încât să se afișeze rezultatul maxim.

ex:

5
4 7 1 5 3

(se afișeaza rezultatul)

44

Explicație (nu se afișează și explicația)

4*7+1+5*3 = 44



Mă gândesc să aflu cele mai mari 2 perechi din șir , adică , în cazul concret,

4,7 și 5,3 și să îl modific ca și înmultire


Aveți idei? Orice idee este binevenită !

Dacă nu ai voie să rearanjezi elementele citite, atunci ai putea folosi un vector auxiliar de produse. În respectivul vector vei pune rezultatul înmulțirii a 2 elemente vecine din vectorul tău inițial.
De exemplu, pentru datele tale, vom avea noul vector v cu următoarele valori :

Din vectorul respectiv, alegi cele mai mari 2 elemente și interpretezi semnele ce trebuie să le pui în felul urmățor : fiind un vector de produse de 2 elemente vecine, cele mai mari 2 valori vor fi înlocuite cu * (produs), iar restul vor fi înlocuite cu + (sumă).
În felul acesta, avem următoarele semne :

Iei noile semne, le intercalezi cu vectorul tău inițial, rezolvi ecuația și-ți ai rezultatul.

Desigur, algoritmul poate fi puternic optimizat. Se poate aborda o metodă greedy în care să se elimine cu totul vectorul v și să se afle rezultatul final încă din bucla de citire a celor n elemente, dar asta presupune o stăpânire desăvârșită a logicii și o înțelegere elementară a conceptului de bază (cel enunțat mai sus). Ai putea chiar tu să încerci (și să nu te dai bătut decât atunci când reușești) să simplifici algoritmul propus, acum, că știi că se poate. Câștigul, vei vedea, va fi mai valoros decât niște puncte obținute într-un concurs.

Spor

@Victor:
Soluția ta este parțial corectă - vezi mai jos un contraexemplu pe care algoritmul propus se comportă ciudat:


Editare ulterioară: se pare că nu am primit enunțul problemei corect - și cele n numere ar fi trebuit să fie naturale. Totuși, îmi mențin afirmația legată de corectitudinea soluției:

Pentru

Răspunsul scos ar fi
Din limitări, nu văd alt rezultat mai bun. Operațiile ar reieși din :

Înțeleg ceva greșit ? Repet : consider că soluția este corectă numai în cazul în care ordinea elementelor citite trebuie să se păstreze conform exemplului lui eric. Dacă nu s-ar fi respectat ordinea, atunci 5*7+1+4*3 = 48 (> 44) ar fi fost o mai bună alegere.

L.E: Sub aceleași considerente, exemplul :

ar scoate:

ceea ce, din câte pot eu să urmăresc, ar fi corect, sau ?

Raspunsul corect este 56.

^ Semnele se pot insera oriunde între elemente ? Nu trebuie să fie intercalate ? În acest caz, corect : am greșit, rezolvarea mea nu este corectă!

Nu...Am rezolvat si eu problema asta cand eram in clasa a IX-a si pierdeam puncte din cauza ca nu luam in calcul ca cele doua semne de inmultire pot fi unul langa altul.

Wow, am terminat-o
Mulțumesc!