Codeforces•May 15, 2025
Hit the Lottery
Hazrat Ali
Codeforces
Allen has a LOT of money. He has nn dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are 11, 55, 1010, 2020, 100100. What is the minimum number of bills Allen could receive after withdrawing his entire balance?
Input
The first and only line of input contains a single integer nn (1≤n≤1091≤n≤109).
Output
Output the minimum number of bills that Allen could receive.
Examples
Input
125
Output
3
Input
43
Output
5
Input
1000000000
Output
10000000
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int m;
cin >> m;
vector<int> s(m), d(m);
for (int i = 0; i < m; i++) {
cin >> s[i] >> d[i];
}
int temp = s[0];
for (int i = 1; i < m; i++) {
int a = 0;
while (s[i] + a * d[i] <= temp) {
a++;
}
temp = s[i] + a * d[i];
}
cout << temp << endl;
return 0;
}