Editing 2150 - Credite

== Enunț ==
Maria este studentă în anul I la facultatea de informatică și a primit o listă de <code>N</code> probleme, numerotate de la <code>1</code> la <code>N</code>, 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 (<code>Ci</code>) pe care studentul le va primi dacă rezolvă problema <code>i</code>, dar și un număr limită de unități de timp (<code>Ti</code>) 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ă <code>numărul maxim</code> de credite pe care le poate obține Maria.

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

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

= Date de ieșire =
În fișierul <code>crediteOUT.txt</code> 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 =

* <code>2 ≤ n ≤ 10000</code>
* <code>2 ≤ Ci ≤ 1000</code>
* <code>1 ≤ Ti ≤ 10000</code>

= Exemplul 1: =
<code>crediteIN.txt</code>
 4
 10 3
 7 5
 8 1
 2 1
<code>crediteOUT.txt</code>
 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: ==
<code>crediteIN.txt</code>
 10001
 10 3
 7 5
 8 1
 2 1
<code>crediteOUT.txt</code>
 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>