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

0

profuout.txt

Datele nu corespund restrictiilor

Rezolvare

<syntaxhighlight lang="python" line>

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