Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Kolejne zadanie o wydawanie reszty. No nie! Znowu?
Dana jest kwota K (reszta), którą chcemy przedstawić w postaci sumy jak najmniejszej liczby składników. Każdy składnik musi należeć do zadanego zbioru (nominałów). A zbiór nominałów składa się z nominałów 10n oraz 25 ⋅ 102n, dla dowolnego nieujemnego całkowitego n. Zatem zbiór nominałów jest następujący: {1, 10, 25, 100, 1 000, 2 500, 10 000, 100 000, 250 000, …}.
Napisz program, który: wczyta wiele kwot do wydania, wyznaczy dla każdej z nich minimalną liczbę nominałów, niezbędnych do wydania tej kwoty i wypisze wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zestawów danych. W kolejnych wierszach znajdują się kolejne zestawy danych.
Opis każdego zestawu danych składa się z jednej liczby naturalnej Ki, określającej kwotę do wydania.
Wyjście
Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego z zestawów danych to jedna liczba całkowita – minimalna liczba nominałów niezbędna do wydania kwoty Ki.
Ograniczenia
1 ≤ Q ≤ 100 000, 1 ≤ Ki ≤ 1017.
Przykład
| Input | Output | |
|
|