NumReverseHard
SRM 855 · 2024-05-22 · by misof
Problem Statement
Take all the positive integers from A to B, inclusive.
Reverse as many of them as you like. (E.g., reversing 1234 changes it into 4321, and reversing 4700 turns it into 0074 = 74.)
Then, add them all up.
Calculate the largest possible result you can get. Return that result modulo (10^9 + 7).
Constraints
- B will be between 1 and 10^18 - 1, inclusive.
- A will be between 1 and B, inclusive.
21 23 Returns: 75
We have the numbers 21, 22, and 23. We can reverse 23 to get 32. This will give us the final sum 21 + 22 + 32 = 75, which is the largest result we can get from these three numbers.
12 21 Returns: 489
Note that after we reverse 12, our collection of numbers will contain two separate 21s. Each of them contributes to the final sum.
97 101 Returns: 495
Here an optimal solution is not to reverse anything.
123 128 Returns: 3426
Here an optimal strategy is to reverse everything.
89 234 Returns: 67841
100000000000000000 100000000000000000 Returns: 300000007
The only number is 10^17. The optimal strategy is not to reverse it (as reversing it changes its value to 1). Thus, the optimal sum is 10^17 and the correct return value is that modulo 10^9 + 7.
Submissions are judged against all 148 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NumReverseHard with a public method int getsum(long long A, long long B) · 148 test cases · 2 s / 256 MB per case