Algorithmen und Datenstrukturen

Der Schokoladenladen

Es stehen n Personen vor einem Laden, der ausschließlich Schokolade verkauft. Jedes Mal, wenn ein Kunde den Schokoladenladen betritt, erhält der Laden 1 kg Schokolade. Sobald der Kunde an die Kasse kommt, kann dieser bereits das soeben eingetroffene 1 kg Schokolade kaufen.
Wir wissen, wie viel Schokolade jede Person in der Warteschlange haben möchte. Falls eine Person den Laden betritt und nicht genug Schokolade vorhanden ist, stellt sie sich wieder ganz hinten an und wartet auf den nächsten Versuch. Wenn sie jedoch genügend Schokolade kaufen kann, nimmt sie diese mit und verlässt den Laden.
Die Aufgabe besteht darin, für jede Person zu bestimmen, wie oft sie den Laden betreten muss, um die gewünschte Menge Schokolade zu erhalten.
Anfangs hat der Laden keinen Schokoladenvorrat.

Eingabe

Die erste Zeile der Eingabe enthält eine einzige ganze Zahl n (1 ≤ n ≤ 10 000).
Die nächste Zeile enthält n durch Leerzeichen getrennte ganze Zahlen, die angeben, wie viel Schokolade jede Person benötigt (1 ≤ ≤ 20).

Ausgabe

Das Programm soll n durch Leerzeichen getrennte ganze Zahlen ausgeben, die angeben, wie oft jede Person den Laden betreten wird.

Beispiele

Eingabe
Ausgabe
3 1 3 2
1 4 1

Erklärung

  1. Der erste Kunde betritt den Laden → der Laden erhält 1 kg Schokolade ⇒ dieses 1 kg kann sofort an den ersten Kunden verkauft werden, sodass er zufrieden den Laden verlässt.
  1. Als Nächstes kommt der zweite Kunde → der Laden erhält 1 kg Schokolade. Da der Kunde aber 3 kg möchte, ist nicht genug vorhanden, und er stellt sich wieder hinten an.
  1. Der dritte Kunde betritt den Laden → der Laden erhält erneut 1 kg Schokolade (insgesamt 2 kg) ⇒ es reicht für den dritten Kunden, der daraufhin den Laden zufrieden verlässt.
  1. Nun betritt der zweite Kunde wieder den Laden → der Laden erhält 1 kg Schokolade. Insgesamt ist erst 1 kg da, aber der Kunde benötigt 3 kg, also verlässt er den Laden erneut.
  1. Der zweite Kunde betritt den Laden erneut → der Laden erhält 1 kg Schokolade. Jetzt sind es 2 kg, der Kunde braucht jedoch 3 kg, also muss er wieder gehen.
  1. Der zweite Kunde betritt den Laden noch einmal → der Laden erhält 1 kg Schokolade (insgesamt 3 kg) ⇒ damit kann er endlich seine 3 kg kaufen und zufrieden gehen.
Somit hat der erste Kunde den Laden nur 1 Mal betreten, der zweite Kunde 4 Mal und der dritte Kunde 1 Mal.

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue