4010 - Mos Craciun 2

Cerinta

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.

Rezolvare

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 - total_cadouri) * 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 minimă necesară:", rezultat)

if __name__ == "__main__":

    main()