SUMSLOPE - Summing Slopes
A digit in a number N is a minima if it is lesser than both the digits adjacent to it. Similarly, a digit is a maxima if it is greater than both the digits adjacent to it. The slope of N is the number of digits in N (leaving out the first and the last digit) which are either a minima or a maxima. Given A and B, count the sum of the slopes of all numbers between A and B.
Input
The first line contains the number of test cases T. Each of the next T lines contains two integers A and B.
Output
Output T lines one for each test case, containing the required sum for the corresponding test case.
Sample
Input 3 101 101 1 100 100 150 Output 1 0 19
Constraints
1 <= T <= 50000
1 <= A <= B <= 1000000000000000 (10^15)
hide comments
|
[Rampage] Blue.Mary:
2017-08-30 06:50:39
With updated compiler C++14, O(digit * base) per test case can easily get AC.
|
|
heathens:
2016-12-27 15:15:28
varun can you pm me how to do digits+base ? im doing it digits*base
|
|
Ivan Katanic:
2010-09-28 07:08:41
well mine is O( digits + base ) per test case too, but usually we should make time limit at least 0.5 s more authors solution runs. |
|
Varun Jalan:
2010-09-28 07:08:41
Increased time limit to 2 seconds. |
|
|
Varun Jalan:
2010-09-28 07:08:41
@ Ivan : My solution takes 0.8 seconds without speed IO. I have O(digits + base) per test case (not O(digits * base)). Last edit: 2010-07-27 07:42:02 |
|
gustav:
2010-09-28 07:08:41
You should seriously consider making the time limit less strict, 1s is ridiculous. Also, as Oleg said, the actual limit on A and B is not 10^9 but 10^15. Last edit: 2010-07-26 21:12:43 |
|
|
Ivan Katanic:
2010-09-28 07:08:41
I think that time limit is too strict, how fast is your solution and do you have any dirty optimizations? |
| Added by: | Varun Jalan |
| Date: | 2010-07-26 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 VB.NET |
| Resource: | own problem |
RSS