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
; profuout.txt
: Datele nu corespund restrictiilor
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2252 - Profu
def check_restrictions(n, k, volumes):
    if not (1 <= n <= 500000):
        return False

    if not all(0 < volume < 1000000 for volume in volumes):
        return False

    return True

def transport_capacity(n, k, volumes):
    if not check_restrictions(n, k, volumes):
        print("Datele nu corespund restrictiilor")
        return None

    volumes.sort(reverse=True)

    left, right = max(volumes), sum(volumes)

    while left < right:
        mid = (left + right) // 2
        required_transports = 1
        current_capacity = 0

        for volume in volumes:
            if current_capacity + volume > mid:
                required_transports += 1
                current_capacity = 0

            current_capacity += volume

        if required_transports <= k:
            right = mid
        else:
            left = mid + 1

    return left

# Citire date de intrare
try:
    with open("profuin.txt", "r") as file:
        n, k = map(int, file.readline().split())
        volumes = list(map(int, file.readline().split()))
except FileNotFoundError:
    print("Fisierul de intrare nu exista!")
    exit()

# Calcul și scriere rezultat în fișierul de ieșire
result = transport_capacity(n, k, volumes)
if result is not None:
    with open("profuout.txt", "w") as file:
        file.write(str(result) + "\n")

</syntaxhighlight>