4009 - Mos Craciun 1

Cerinta

Moș Crăciun pregătește cadourile pentru acest an. El cunoaște prețurile a n cadouri și are la dispoziție o sumă de bani S. Ajutați-l să aleagă un număr maxim de cadouri a căror preț total să nu depășească S și determinați suma minimă de care mai are nevoie Moș Crăciun pentru a cumpăra încă un cadou.

Date de intrare

Programul citește de la tastatură numerele n S, iar apoi n numere naturale, reprezentând prețurile cadourilor.

Date de iesire

Programul va afișa pe ecran două numere, k p, separate printr-un spațiu, reprezentând numărul maxim de cadouri pe care le poate cumpăra Moș Crăciun și suma minimă de care mai are nevoie pentru a cumpăra încă un cadou.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ S ≤ 1 000 000 000
• prețurile cadourilor vor fi mai mici decât 1 000 000

Rezolvare

def validate_input(n, S, preturi):
    if not (1 <= n <= 1000):
        raise ValueError("Numărul de cadouri trebuie să fie între 1 și 1000.")

    if not (1 <= S <= 1000000000):
        raise ValueError("Suma disponibilă trebuie să fie între 1 și 1 000 000 000.")

    if not all(0 < pret < 1000000 for pret in preturi):
        raise ValueError("Prețurile cadourilor trebuie să fie mai mici decât 1 000 000.")

def mos_craciun(n, S, preturi):
    preturi.sort()  # Sortăm prețurile cadourilor în ordine crescătoare
    suma_cheltuita = 0
    numar_cadouri = 0
    for pret in preturi:
        if suma_cheltuita + pret <= S:  # Dacă putem cumpăra acest cadou
            suma_cheltuita += pret
            numar_cadouri += 1
        else:
            break
    suma_necesara = max(0, pret - (S - suma_cheltuita))  # Calculăm suma minimă necesară pentru următorul cadou
    return numar_cadouri, suma_necesara

def mos_craciun(n, S, preturi):
    preturi.sort()  # Sortăm prețurile cadourilor în ordine crescătoare
    suma_cheltuita = 0
    numar_cadouri = 0
    for pret in preturi:
        if suma_cheltuita + pret <= S:  # Dacă putem cumpăra acest cadou
            suma_cheltuita += pret
            numar_cadouri += 1
        else:
            break
    suma_necesara = max(0, pret - (S - suma_cheltuita))  # Calculăm suma minimă necesară pentru următorul cadou
    return numar_cadouri, suma_necesara

def main():
    n, S = map(int, input("Introduceți numărul de cadouri și suma de bani disponibilă (S): ").split())
    preturi = list(map(int, input("Introduceți prețurile cadourilor: ").split()))
    k, p = mos_craciun(n, S, preturi)
    print(f"Numărul maxim de cadouri: {k}")
    print(f"Suma minimă necesară pentru încă un cadou: {p}")

if __name__ == "__main__":
    main()