Swiss Olympiad in Informatics

In Stofls Büro befindet sich ein Geldautomat der IBM (Internationale Mäusebank). Stofl und seine vielen Mitarbeiter benutzen den Geldautomaten recht oft, an guten Tagen bis zu 10000 mal. Deshalb ist es nicht auszuschliessen, das einmal während eines Bezugs ein Fehler auftritt.

Um solche Fehler zu finden, schreibst du ein Computerprogramm, das die Bezüge dieses Geldautomaten simuliert.

Die IBM füllt den Automaten jeden Morgen mit Banknoten (1000er-, 200er-, 100er-, 50er-, 20er- und 10er-Noten) und Münzen (Fünf-, Zwei- und Einfrankenstücke).

Die Kunden der IBM möchten nicht unnötig viele kleine Noten und Münzen in Ihren Portemonnaies. Wenn ein Automat die Beträge nur noch in kleinen Noten oder Münzen auszahlen kann, gehen sie lieber zu einem anderen Automaten. Da die IBM Ihre Kunden nicht verärgern will, zahlen ihre Geldautomaten den gewünschten Betrag gar nicht aus, wenn er nur in kleinen Noten oder Münzen ausbezahlt werden könnte. Wenn eine Maus zum Beispiel 16 Franken abheben will (was normalerweise die Ausgabe von einer Zehnernote, einem Fünf- und einem Einfrankenstück bedeuten würde), sich aber im Automaten keine Fünffrankenstücke mehr befinden, führt der Automat den Bezug nicht durch, selbst wenn z. B. genug Einfrankenstück vorhanden wären, um 16 Franken auszugeben.

Du erhältst die genaue Anzahl Noten und Münzen jeder Sorte, die sich am Morgen im Geldautomaten befinden, sowie eine Liste der angeforderten Bezüge während eines bestimmten Tages. Gib die Anzahl Münzen und Noten aus, die sich am Ende des Tages im Automaten befinden.

Die erste Zeile enthält neun Integer: A₁,…,A₉, Die Anzahl der 1000-, 200-, 100-, 50-, 20-, 10-, 5-, 2-, 1-Franken-Noten und -Münzen am Morgen des simulierten Tages. Du kannst annehmen, dass 0≤A_i≤10'000, für i=1..9 gilt. Die nächste Zeile enthält einen Integer N (N<10'000), die Anzahl der an diesem Tag angeforderten Bezüge. Die nächsten N Zeilen enthalten je einen Integer k_i (0≤k_i≤1'000'000). Sie beschrieben die Angeforderten Bezüge an diesem Tag in chronologischer Reihenfolge.

Eine Zeile mit neun Integern B₁,…,B₉, die Anzahl der 1000-, 200-, 100-, 50-, 20-, 10-, 5-, 2-, 1-Franken-Noten und -Münzen am Abend desselben Tages, nach den N Bezügen.

0 0 0 0 0 4 3 2 1
6
11
20
3
55
7
4

0 0 0 0 0 3 2 1 0

• Im Beispiel sind am Morgen vier Zehnernoten, drei Fünffrankenstücke, zwei Zweifrankenstücke und ein Einfrankenstück im Automaten, und es werden 6 Bezüge ausgeführt.
• Der erste Bezug von 11 Franken kann mit einer Zehnernote und einem Einfrankenstück ausbezahlt werden.
• Die 20 Franken können nicht ausbezahlt werden, da keine Zwanzigernote vorhanden ist. Deshalb wird kein Geld ausgegeben, obwohl sich drei Zehnernoten im Automaten befinden.
• Der folgende Bezug von 3 Franken kann nicht ausbezahlt werden, da es kein Einfrankenstück mehr im Automaten hat.
• Der Bezug vom 55 Franken kann ebenfalls nicht ausbezahlt werden, da keine Fünfzigernote im Automaten ist.
• Der Bezug von 7 Franken wird mit einem Fünf- und einem Zweifrankenstück ausbezahlt.
• Der letzte Bezug von 4 Franken kann nicht ausbezahlt werden, da nur noch ein Zweifrankenstück im Automaten ist.

Submission form