1096 - Expresie 8

Costel are de rezolvat o temă grea la matematică: având la dispoziţie N numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi N-3 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ă N=5 şi numerele sunt 4, 7, 1, 5, 3, operaţiile pot fi aşezate 4+7*1+5*3, 4*7*1+5+3, e.t.c

Cerinţă

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

Date de intrare

Fișierul de intrare expresie8.in are următoarea structură:

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

Date de ieșire

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

Restricții și precizări

• 4 <= N <= 1000
• Numerele date sunt numere naturale între 1 şi 10000

Exemplu:

expresie8.in

5
4
7
1
5
3

expresie8.out

44

Explicație

Valoarea maximă se obţine prin aşezarea operaţiilor sub forma: 4 * 7 + 1 + 5*3.

Încărcare soluție

Lipește codul aici

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")