2245 - Plata 1

Cerința

Se consideră n tipuri de bancnote, cu valorile v[1] v[2] ... v[n], ordonate strict crescător. Pentru fiecare tip de bancnote se știe numărul de bancnote disponibile c[1] c[2] ... c[n]. Se cere să se determine o modalitate de a plăti integral o sumă dată S cu bancnotele disponibile.

Date de intrare

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

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 1 ≤ c[i] ≤ 10 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 6 3 4 6 1 Ieșire

5 0 2 5 1

Explicație

Se folosesc cinci bancnote de 1 leu, două de 10 lei, cinci de 50 de lei și una de 100 de lei: 5 * 1 + 2 * 10 + 5 * 50 + 1 * 100 = 375.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def plata_bancnote(n, S, valori, cantitati):

  rezultat = [0] * n
  suma_actuala = 0
  for i in range(n - 1, -1, -1):
      while suma_actuala + valori[i] <= S and cantitati[i] > 0:
          suma_actuala += valori[i]
          cantitati[i] -= 1
          rezultat[i] += 1
  return rezultat

if __name__ == "__main__":

  # Citim datele de intrare
  n, S = map(int, input().split())
  valori = list(map(int, input().split()))
  cantitati = list(map(int, input().split()))
  # Apelăm funcția pentru a obține rezultatul
  rezultat = plata_bancnote(n, S, valori, cantitati)
  # Afișăm rezultatul
  print(*rezultat)

python plata_bancnote.py </syntaxhighlight>