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

<syntaxhighlight lang="python"> 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()

</syntaxhighlight>