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

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