3170 - Plata 3

Cerința

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile, știind că se pot folosi oricâte bancnote de orice tip.

Date de intrare

Programul citește de la tastatură numerele n și S, apoi valorile v[1] v[2] ... v[n] ale bancnotelor.

Date de ieșire

Programul va afișa pe ecran n numere, reprezentând o modalitate de plată a sumei S. Fiecare număr x[i] va reprezenta numărul de bancnote de valoarea x[i] folosite pentru plata sumei S.

Restricții și precizări

1 ≤ n ≤ 6 1 ≤ S ≤ 1000 1 ≤ v[i] ≤ 100 oricare variantă corectă de plată a sumei S va fi luată în considerare pentru toate seturile de date există soluție ==Exemplu==: Intrare

5 375 1 5 10 50 100 Ieșire

5 2 1 1 3

Observații

Există și alte soluții valide.

Rezolvare

def plata_bancnote(n, S, valori):

   rezultat = [0] * n
   suma_ramasa = S
   for i in range(n - 1, -1, -1):
       bancnote_folosite = suma_ramasa // valori[i]
       rezultat[i] = bancnote_folosite
       suma_ramasa -= bancnote_folosite * valori[i]
   return rezultat

if __name__ == "__main__":

   # Citire date de intrare
   n, S = map(int, input().split())
   valori = list(map(int, input().split()))
   # Calcul și afișare rezultat
   rezultat = plata_bancnote(n, S, valori)
   print(*rezultat)

python plata_bancnote_flexibil.py