Editing 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 *.
<br>
Îş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
<br>
== Exemplul 2 ==
; optimin.txt
: 8 2
: -3
: 5
: 2
: 4
: -1
: 0
: -2
: 7
; optimout.txt
: -54 840
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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

# 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()))

# Calculăm valorile minime și maxime
result = calc_min_max_values(N, K, numbers)

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