1760 - Optim

Gigel primea de la mama lui, ca temă, o foaie pe care era scris un şir de N numere întregi. Singurul calcul pe care ştia să îl facă până acum era suma tuturor numerelor. Pentru aceasta el plasa N-1 semne de adunare, +, între numerele aflate pe poziţii consecutive în şir şi calcula astfel suma acestor numere. Între timp a crescut şi a învăţat şi operaţia de înmulţire pentru care foloseşte semnul *. Din şirul celor N-1 semne de adunare, îi trece prin minte să înlocuiască K semne + cu K semne *.

Îşi dă seama că tema se complică, deoarece înmulţirile trebuie efectuate înaintea adunărilor, dar nu se dă bătut şi duce calculul până la capăt.

Cerința

Scrieţi un program care să determine valoarea minimă pe care o poate obţine şi valoarea maximă pe care o poate obţine după înlocuirea menţionată.

Date de intrare

Fişierul de intrare optimIN.txt conţine pe prima linie numerele naturale N şi K, separate printr-un spaţiu, reprezentând numărul de numere întregi din şir, respectiv numărul de operaţii de înmulţire ce vor fi efectuate. Pe cea de a doua linie se află N numere întregi separate prin câte un spaţiu, , reprezentând numerele din şir.

Date de ieșire

Fişierul de ieşire optimOUT.txt va conţine pe o singură linie, separate printr-un spaţiu, în ordine crescătoare, cele două valori cerute. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 2 ≤ N ≤ 30
• 0 ≤ K ≤ 9; K < N
• -8 ≤ xi ≤ 8, 1 ≤ i ≤ N

Exemplu 1:

optimIN.txt

6 3
2
0
3
-1
7
-4

optimOUt.txt

-31 86

Explicație

2 * 0 + 3 * (-1) + 7 * (-4) = -31

2 + 0 + 3 * (-1) * 7 * (-4) = 86.

Exemplu 2:

optimIN.txt

6 8
2
0
3
-1
7
-4

optimOUt.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verificare_restrictii(N, K, A):
    if not (2 <= N <= 30) or not (0 <= K <= 9) or not (K < N):
        return False
    if not all(-8 <= x <= 8 for x in A):
        return False
    return True

def back(lv, k, aux, suma, A, N):
    global maxim, minim
    if lv == N:
        suma += aux
        if suma > maxim:
            maxim = suma
        if suma < minim:
            minim = suma
        return
    if N - lv > k:
        back(lv + 1, k, A[lv], suma + aux, A, N)
    if k > 0:
        back(lv + 1, k - 1, aux * A[lv], suma, A, N)

def main():
    global maxim, minim
    
    with open("optimIN.txt", "r") as fin:
        N, K = map(int, fin.readline().strip().split())
        A = [int(fin.readline().strip()) for _ in range(N)]
    
    if not verificare_restrictii(N, K, A):
        with open("optimOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return
    
    maxim = -2000000000
    minim = 2000000000
    
    back(1, K, A[0], 0, A, N)
    
    with open("optimOUT.txt", "w") as fout:
        fout.write(f"{minim} {maxim}\n")

if __name__ == "__main__":
    main()