NONDEC - Non-Decreasing Numbers
A Non-Decreasing number is a number whose ith digit from the left is greater than or equal to the (i-1)th digit from the left.
You are given four integers A, B, C and D. X is any integer between A and B, inclusive, and Y is any integer between C and D, inclusive. You must output the number of numbers formed by the concatenation of X and Y which are Non-Decreasing, i.e. if we treat "X" and "Y" as STRINGS, then "Z" = "X" + "Y" must represent a Non-Decreasing number.
Since this number can be very large, give your answer modulo 98765431.
If the same number "Z" can be formed in various ways, it must be counted every time. See example for clarification.Input
The first line of the input contains t, the number of test cases. This is followed by t lines containing 4 positive integers each, which are the values of A, B, C, D.
Output
You must output t lines. Each line contains the answers for the quadruple (A, B, C, D) in the order they appear in input.
Example
Input:
1
1 11 1 11 Output: 56
Explanation
Note that the number "111" is counted twice. Once as "11" + "1" and again as "1" + "11".
Constraints
A, B, C, D are all positive integers having <= 1000 digits
A <= B; C <= D;
Number of test cases = t <= 1000
hide comments
Ehor Nechiporenko:
2012-11-22 15:53:44
It was a long way to resolve this task. But I am happy to finally created the correct solution. Thanks a lot to problem setter! |
Added by: | Kunal Jain |
Date: | 2011-02-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CodeCraft 11 |