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

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

Explicatie

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

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