4010 - Mos Craciun 2

Cerința

Moș Crăciun pregătește cadourile pentru acest an. El trebuie să dea cadouri identice la n copii. Pentru aceasta, a vizitat m magazine (posibil online) și pentru fiecare magazin a aflat prețul cadoului în acel magazin și numărul de cadouri disponibile în acel magazin.

Determinati suma minimă necesară pentru a cumpăra cele n cadouri necesare. Dacă nu se pot cumpăra cele n cadouri afișați mesajul imposibil.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi m perechi numere naturale p c, reprezentând prețul și cantitatea de cadouri disponibile în cele n magazine.

Date de iesire

Programul va afișa pe ecran suma totală necesară S sau mesajul imposibil.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 100
• 0 ≤ c ≤ 100
• 1 ≤ p ≤ 100

Exemplu:

Intrare

5 3

2 1

4 5

3 2

Ieșire

16

Explicație

Moș Crăciun va cumpăra un cadou cu prețul 2, două cu prețul 3 și două cu prețul 4.

Rezolvare

<syntaxhighlight lang="python"> def suma_minima(n, m, magazine):

   magazine = sorted(magazine, key=lambda x: x[0])  # Sortăm magazinele după preț
   total_cadouri = 0
   suma = 0

   for pret, cantitate in magazine:
       if total_cadouri + cantitate >= n:  # Dacă avem suficiente cadouri
           suma += n * pret
           break
       suma += cantitate * pret
       total_cadouri += cantitate

   if total_cadouri < n:
       return -1  # Imposibil de cumpărat n cadouri
   else:
       return suma  # Suma minimă necesară

def main():

   n, m = map(int, input("Introduceți numărul de copii (n) și numărul de magazine (m): ").split())
   magazine = []

   print("Introduceți prețul și cantitatea disponibilă pentru fiecare magazin:")

   for _ in range(m):
       p, c = map(int, input().split())
       magazine.append((p, c))

   rezultat = suma_minima(n, m, magazine)

   if rezultat == -1:
       print("Imposibil")
   else:
       print("Suma minima necesara:", rezultat)

if __name__ == "__main__":

   main()

</syntaxhighlight>