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

def validare_intrare(n, m, magazine):
    if not (1 <= n <= 1000):
        print("Eroare: n trebuie să fie între 1 și 1000.")
        return False

    if not (1 <= m <= 100):
        print("Eroare: m trebuie să fie între 1 și 100.")
        return False

    for i, (pret, cantitate) in enumerate(magazine):
        if not (0 <= cantitate <= 100):
            print(f"Eroare la magazinul {i + 1}: Cantitatea trebuie să fie între 0 și 100.")
            return False

        if not (1 <= pret <= 100):
            print(f"Eroare la magazinul {i + 1}: Prețul trebuie să fie între 1 și 100.")
            return False

    return True
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()