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, x1,x2,…xN , 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.

Restricții și precizări

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

Exemplul 1

optimin.txt

6 3

2

0

3

-1

7

-4

optimout.txt

-31 86

Exemplul 2

optimin.txt

8 2

-3

5

2

4

-1

0

-2

7

optimout.txt

-54 840

Rezolvare

<syntaxhighlight lang="python" line>

1. 1760 - Optim

def calc_min_max_values(N, K, numbers):

   # Verificăm restricțiile
   if not (2 <= N <= 30) or not (0 <= K < N):
       return "Fals"

   # Inițializăm valorile minime și maxime cu suma inițială
   min_value = sum(numbers)
   max_value = sum(numbers)

   # Generăm toate combinațiile de poziții pentru înmulțire
   for i in range(1 << (N - 1)):
       # Convertim i la binar și adăugăm zerouri la început pentru a obține o reprezentare cu N-1 cifre binare
       binary_repr = bin(i)[2:].zfill(N - 1)

       # Calculăm suma pentru configurația curentă
       current_sum = numbers[0]
       current_multiply_count = 0

       for j in range(N - 1):
           if binary_repr[j] == '0':
               current_sum += numbers[j + 1]
           else:
               current_sum *= numbers[j + 1]
               current_multiply_count += 1

       # Actualizăm valorile minime și maxime
       min_value = min(min_value, current_sum)
       max_value = max(max_value, current_sum)

       # Verificăm dacă numărul de înmulțiri este cel dorit (K)
       if current_multiply_count == K:
           break

   return min_value, max_value

1. Citim datele de intrare din fișierul "optimin.txt"

with open("optimin.txt", "r") as file:

   N, K = map(int, file.readline().split())
   numbers = list(map(int, file.readline().split()))

1. Calculăm valorile minime și maxime

result = calc_min_max_values(N, K, numbers)

1. Scriem rezultatele în fișierul "optimout.txt" sau afișăm "Fals" în cazul în care restricțiile nu sunt respectate

with open("optimout.txt", "w") as file:

   if isinstance(result, tuple):
       file.write(f"{result[0]} {result[1]}")
   else:
       file.write(result)

</syntaxhighlight>

Explicatie

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

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