SPOJ Problem Set (classical)

6986. Summing Slopes

Problem code: SUMSLOPE

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

Sample Output :
1
0
19

Constraints :
1 <= T <= 50000
1 <= A <= B <= 1000000000000000 (10^15)

Added by:	Varun Jalan
Date:	2010-07-26
Time limit:	2s
Source limit:	50000B
Memory limit:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Languages:	All except: NODEJS PERL 6
Resource:	own problem

hide comments



2010-09-28 09:08:41 Ivan Katanić 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.
2010-09-28 09:08:41 Varun Jalan Increased time limit to 2 seconds.
2010-09-28 09:08:41 Varun Jalan @ 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 09:42:02
2010-09-28 09:08:41 Gustav Matula 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 23:12:43
2010-09-28 09:08:41 Ivan Katanić I think that time limit is too strict, how fast is your solution and do you have any dirty optimizations?