Aurelia Raluca: Pagină nouă: == 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 stud...

2024-03-23T00:30:27Z

Pagină nouă: == 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 stud...

New page

== 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>

2150 - Credite - Revision history