Editing 1096 - Expresie 8

Costel are de rezolvat o temă grea la matematică: având la dispoziţie <code>N</code> numere naturale nenule trebuie să aşeze între acestea <code>2</code> operaţii de înmulţire şi <code>N-3</code> operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date.

De exemplu, dacă <code>N=5</code> şi numerele sunt <code>4</code>, <code>7</code>, <code>1</code>, <code>5</code>, <code>3</code>,  operaţiile pot fi aşezate <code>4+7*1+5*3</code>, <code>4*7*1+5+3</code>, e.t.c

= Cerinţă =
Scrieţi un program care să aşeze două operaţii de înmulţire şi <code>N-3</code> operaţii de adunare între cele <code>N</code> valori date astfel încât valoarea expresiei obţinute să fie maximă.

= Date de intrare =
Fișierul de intrare <code>expresie8.in</code> are următoarea structură:

* Pe prima linie se află un număr natural <code>N</code>, reprezentând numărul elementelor date.
* Pe următoarele linii se află cele <code>N</code> numere naturale date, fiecare pe câte o linie.

= Date de ieșire =
Fișierul de ieșire <code>expresie8.out</code> va conține pe prima linie valoarea maximă obţinută prin evaluarea expresiei.

= Restricții și precizări =

* <code>4 <= N <= 1000</code>
* Numerele date sunt numere naturale între <code>1</code> şi <code>10000</code>

= Exemplu: =
<code>expresie8.in</code>
 5
 4
 7
 1
 5
 3
<code>expresie8.out</code>
 44

= Explicație =
Valoarea maximă se obţine prin aşezarea operaţiilor sub forma: <code>4 * 7 + 1 + 5*3</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
with open("expresie8.in", "r") as fin, open("expresie8.out", "w") as fout:
    n = int(fin.readline())
    v = list(map(int, fin.readline().split()))
    
    s = 0
    Max = 0
    for i in range(1, n+1):
        s += v[i]
    
    for i in range(1, n-1):
        cc = s - v[i] - v[i+1] - v[i+2] + (v[i] * v[i+1] * v[i+2])
        if cc > Max:
            Max = cc
    
    for i in range(1, n-2):
        for j in range(i+2, n):
            cc = s - v[i] - v[i+1] - v[j] - v[j+1] + (v[i] * v[i+1]) + (v[j] * v[j+1])
            if cc > Max:
                Max = cc
                
    fout.write(str(Max) + "\n")
</syntaxhighlight>