Editing 1760 - Optim

Gigel primea de la mama lui, ca temă, o foaie pe care era scris un şir de <code>N</code> numere întregi. Singurul calcul pe care ştia să îl facă până acum era suma tuturor numerelor. Pentru aceasta el plasa <code>N-1</code> 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 <code>N-1</code> semne de adunare, îi trece prin minte să înlocuiască <code>K</code> semne + cu <code>K</code> 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 <code>optimIN.txt</code> conţine pe prima linie numerele naturale <code>N</code> şi <code>K</code>, 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ă <code>N</code> numere întregi separate prin câte un spaţiu, , reprezentând numerele din şir.

= Date de ieșire =
Fişierul de ieşire <code>optimOUT.txt</code> 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 =

* <code>2 ≤ N ≤ 30</code>
* <code>0 ≤ K ≤ 9; K < N</code>
* <code>-8 ≤ xi</code> <code>≤ 8,  1 ≤ i ≤ N</code>

= Exemplu 1: =
<code>optimIN.txt</code>
 6 3
 2
 0
 3
 -1
 7
 -4
<code>optimOUt.txt</code>
 -31 86

=== Explicație ===
<code>2 * 0 + 3 * (-1)  + 7 * (-4)  = -31</code>

<code>2 + 0 + 3 * (-1)  * 7 * (-4)  = 86</code>.

= Exemplu 2: =
<code>optimIN.txt</code>
 6 8
 2
 0
 3
 -1
 7
 -4
<code>optimOUt.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
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()

</syntaxhighlight>