2150 - Credite

Enunț

Maria este studentă în anul I la facultatea de informatică și a primit o listă de N probleme, numerotate de la 1 la N, pe care trebuie să le rezolve la cursul de algoritmică, rezolvarea unei probleme durând exact o unitate de timp. Pentru că profesorul vrea să testeze capacitatea elevilor de a a face cele mai bune alegeri, pentru fiecare problemă acesta a stabilit numărul de credite (Ci) pe care studentul le va primi dacă rezolvă problema i, dar și un număr limită de unități de timp (Ti) până la care problema poate fi rezolvată.

Cerința

Cunoscând numărul de probleme, numărul de credite al fiecărei probleme precum și timpul limită de rezolvare al fiecărei probleme, scrieți un algoritm care determină numărul maxim de credite pe care le poate obține Maria.

Date de intrare

Pe prima linie a fișierului de intrare crediteIN.txt se găsește un număr natural N, reprezentând numărul de probleme de pe listă.

Pe următoarele N linii din fișierul de intrare vor fi datele despre fiecare problemă, pe linia i+1 găsindu-se 2 numere naturale Ci și Ti care reprezintă numărul de credite, respectiv timpul limită pentru problema i.

Date de ieșire

În fișierul crediteOUT.txt se va afișa un singur număr natural, reprezentând numărul maxim de credite pe care Maria le poate obține.

Restricții și precizări

• 2 ≤ n ≤ 10000
• 2 ≤ Ci ≤ 1000
• 1 ≤ Ti ≤ 10000

Exemplul 1:

crediteIN.txt

4
10 3
7 5
8 1
2 1

crediteOUT.txt

25

Explicație

Maria alege să rezolve problema 3, renunțând la problema 4 pentru ca are mai puține credite și același timp limită ca problema 3. După aceea va rezolva problemele 1 și 2, adunând în total 25 de credite.

Exemplul 2:

crediteIN.txt

10001
10 3
7 5
8 1
2 1

crediteOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> import heapq

def verifica_restrictii(n, v):

   if not (2 <= n <= 10000):
       return False

   for nrC, timpul in v:
       if not (2 <= nrC <= 1000) or not (1 <= timpul <= 10000):
           return False
   
   return True

def main():

   with open("crediteIN.txt", "r") as fin, open("crediteOUT.txt", "w") as fout:
       n = int(fin.readline())
       ans = 0
       v = []
       timp = [False] * 10001
       tmax = 0

       for _ in range(n):
           line = fin.readline().strip()
           if not line:
               continue  # Ignoră liniile goale

           vals = line.split()
           if len(vals) < 2:
               fout.write("Datele din fisier nu sunt formatate corect")
               return
           
           nrC, timpul = map(int, vals)
           v.append((nrC, timpul))
           if timpul > tmax:
               tmax = timpul
           timp[timpul] = True

       if not verifica_restrictii(n, v):
           fout.write("Datele nu corespund restrictiilor impuse")
           return

       q = []

       for i in range(tmax, 0, -1):
           if timp[i]:
               for nrC, timpul in v:
                   if timpul == i:
                       heapq.heappush(q, (-nrC, timpul))

           if q:
               nrC, timpul = heapq.heappop(q)
               ans += -nrC
   
       fout.write(str(ans))

if __name__ == "__main__":

   main()

</syntaxhighlight>