3739 - Cafea

Cerința

Algorel a primit de la părinţi o sumă de bani, S, şi o plasă în care încap K grame de cafea. Algorel trebuie să meargă la piaţă şi să cumpere suficientă cafea încât să umple plasa. Pe de altă parte, părinţii nu îi cer înapoi restul. Dacă va reuşi să umple plasa, va putea păstra diferenţa de bani dintre suma primită S şi costul total al cafelei achiziţionate. Dacă nu va reuşi să umple plasa, atunci nu va rămâne cu niciun ban.

La piaţă există N comercianţi care vând cafea. Fiecare dintre aceştia are o cantitate de Ci grame de cafea pe care o vinde cu preţul total de Pi lei (1 ≤ i ≤ N). Comercianţii nu au monede mai mici de 1 leu, aşa că, în cazul în care clientul cumpără o cantitate de cafea al cărei preţ nu este un număr întreg, acesta va plăti suma rotunjită la cea mai apropiată valoare întreagă mai mare sau egală cu valoarea datorată. De exemplu, dacă un comerciant vinde 1000 de grame de cafea la preţul de 25 de lei şi un client vrea să cumpere 250 de grame, atunci acesta va plăti 7 lei, deşi suma datorată era de 6.25 lei. Ajutaţi-l pe Algorel să rămână cu o sumă cât mai mare de bani, scriind un program care face acest calcul pe baza datelor corespunzătoare comercianţilor.

Date de intrare

Fişierul de intrare cafea.in va conţine pe prima linie, separate prin câte un spaţiu numerele naturale K, S şi N corespunzătoare capacităţii plasei, sumei pe pare o primeşte de la părinţi şi numărului de vânzători. Pe următoarele N linii se vor afla datele corespunzătoare comercianţilor: pe linia i + 1 se vor afla numerele naturale Ci şi Pi reprezentând cantitatea maximă de cafea pe care o vinde comerciantul numărul i şi preţul total cerut de acesta.

Date de ieșire

Fișierul de ieșire cafea.out va conține pe prima linie un număr natural, reprezentând suma maximă care îi rămâne lui Algorel după ce umple plasa cu cafea.

Restricții și precizări

• 1 ≤ K ≤ 1 000 000 000
• 1 ≤ S ≤ 1 000 000 000
• 1 ≤ N ≤ 100 000
• Ci ∈ [1, 100 000], pentru 1 ≤ i ≤ N
• Pi ∈ [1, 100 000], pentru 1 ≤ i ≤ N

Exemplu 1

Intrare

1000 200 4
500 85
600 45
250 35
1000 1000

Iesire

94

Rezolvare

<syntaxhighlight lang="python" line> def main():

   with open("cafea.in", "r") as f:
       k, s, n = map(int, f.readline().strip().split())
       comercianti = []
       for _ in range(n):
           ci, pi = map(int, f.readline().strip().split())
           comercianti.append((pi / ci, ci, pi))  # (preț per gram, cantitate maximă, preț total)

   # Sortăm comercianții după prețul per gram
   comercianti.sort()

   cantitate_cumparata = 0
   cost_total = 0

   for pret_per_gram, cantitate_max, pret_total in comercianti:
       if cantitate_cumparata + cantitate_max <= k:
           cantitate_cumparata += cantitate_max
           cost_total += pret_total
       else:
           cantitate_necesara = k - cantitate_cumparata
           cost_total += cantitate_necesara * pret_per_gram
           cantitate_cumparata += cantitate_necesara
           break

   bani_ramasi = s - cost_total

   with open("cafea.out", "w") as f:
       f.write(f"{int(bani_ramasi)}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>