NumReverseHard | Topcoder Archive

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).

Definition

Class:: NumReverseHard
Method:: getsum
Parameters:: long, long
Returns:: int
Method signature:: int getsum(long A, long B)
(be sure your method is public)

Constraints

B will be between 1 and 10^18 - 1, inclusive.
A will be between 1 and B, inclusive.

Examples

```
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.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.