Einfaches Münzwechsel-Problem
In Armenien gibt es 6 verschiedene Münztypen, von denen jede einen eigenen Wert hat. Die Werte sind 10, 20, 50, 100, 200 und 500. Stellen Sie sich vor, Sie stehen an der Kasse in einem Geschäft und möchten die Rechnung mit möglichst wenigen Münzen begleichen. Können Sie ein Programm schreiben, das berechnet, wie viele Münzen dafür mindestens benötigt werden?
Eingabe
Die einzige Zeile der Eingabe enthält eine ganze Zahl
b (10 ≤ b ≤ ) – den Betrag, den Sie im Geschäft zahlen müssen.Ausgabe
Das Programm soll die minimale Anzahl an Münzen ausgeben, mit denen Sie diesen Betrag bezahlen können.
Beispiele
Eingabe | Ausgabe |
30 | 2 |
90 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB