Editing 2252 - Profu

== Cerința ==
Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:

Avem '''n''' cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr '''A[i]''' reprezentând volumul cutiei '''i = 1,2...,n'''. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim '''k''' transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă '''x''' necesară pentru a efectua cele '''k''' transporturi. Numărul '''x''' este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!
== Date de intrare ==
Pe prima linie a fișierului '''profuin.txt''' se vor găsi cele doua numere '''n''' și '''k''' cu semnificația din enunț apoi pe a doua linie a fișierului se vor găsi '''n''' numere naturale.
== Date de ieșire ==
Fișierul de ieșire '''profuout.txt''' va conține pe prima linie numărul '''x''', reprezentând capacitatea minima a mașini ce trebuie închiriată.
== Restricții și precizări ==
*'''1 &les; n &les; 500.000'''
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000'''
== Exemplu 1 ==
; '''profuin.txt'''
:6 3
:7 3 2 3 1 4
; '''profuout.txt'''
:8
<br>
== Explicatie ==
La primul transport este încărcată prima saltea (care are volumul '''7'''). La cel de-al doilea transport sunt încărcate saltele '''2''' și '''3''' (volumul total este '''3 + 2 = 5'''). La cel de-al treilea transport sunt încărcate saltele '''4''', '''5''' și '''6''' (volumul total este '''3 + 1 + 4 = 8''' fiind cel mai mic rezultat posibil)
== Exemplu 2 ==
; '''profuin.txt'''
: 0
: 0
; '''profuout.txt'''
: DNumarul nu respecta restrictiile.
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
#2252 - Profu
def capacitate_minima(n, k, volumes):
    left, right = max(volumes), sum(volumes)

    while left < right:
        mid = (left + right) // 2
        transports, current_sum = 0, 0

        for volume in volumes:
            if current_sum + volume > mid:
                transports += 1
                current_sum = 0

            current_sum += volume

        transports += 1  # pentru ultimul transport
        if transports > k:
            left = mid + 1
        else:
            right = mid

    return left


try:
    # Citirea datelor de intrare
    with open('profuin.txt', 'r') as f:
        n, k = map(int, f.readline().split())
        volumes = list(map(int, f.readline().split()))

    # Calculul capacitatii minime si scrierea rezultatului in fisierul de iesire
    result = capacitate_minima(n, k, volumes)
    with open('profuout.txt', 'w') as g:
        g.write(str(result))
except Exception as e:
        # În caz de eroare, afișăm un mesaj corespunzător
        with open('profuout.txt', 'w') as f:
            f.write('Numarul nu respecta restrictiile.')

</syntaxhighlight>