Problem Link
Loop ThroughAuthor:shail121
Difficulty
EASYPrerequisites
MathProblem Statement
Lavanya loves vintage-inspired shopping; however, due to the pandemic conditions, she cannot go shopping outside. Her shopping card has p points initially. She plans to perform online shopping to utilize her points. Lavanya chooses some positive integer number x(1≤x≤p) to buy items that cost exactly x points and obtain ⌊x|10⌋ points as a cashback. The operation ⌊a|b⌋ means a divided by b rounded down. It is guaranteed that you can always buy some item that costs x for any possible value of x.Your task is to say the maximum number of points Lavanya can spend if he buys items optimally. You have to answer t independent test cases.
Approach
Let's do the following greedy solution: it is obvious that when we buy food that costs exactly 10k for k≥1, we don't lose any points because of rounding. Let's take the maximum power of 10 that is not greater than p (let it be 10c), buy food that costs 10c (and add this number to the answer) and add 10c−1 to p. Apply this process until p<10 and then add s to the answer.Solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t–) {
int s;
cin >> s;
int ans = 0;
int pw = 1000 * 1000 * 1000;
while (s > 0) {
while (s < pw) pw /= 10;
ans += pw;
s -= pw - pw / 10;
}
cout << ans << endl;
}
return 0;
}
