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 ⩽ n ⩽ 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

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

Rezolvare

<syntaxhighlight lang="python" line>

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

1. 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()

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