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.

Rezolvare

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