NUMTSN - 369 Numbers
7. 369 numbers
A number is said to be a 369 number if
- The count of 3s is equal to count of 6s and the count of 6s is equal to count of 9s.
- The count of 3s is at least 1.
For Example 12369, 383676989, 396 all are 369 numbers whereas 213, 342143, 111 are not.
Given A and B find how many 369 numbers are there in the interval [A, B]. Print the answer modulo 1000000007.
Input
The first line contains the number of test cases (T) followed by T lines each containing 2 integers A and B.
Output
For each test case output the number of 369 numbers between A and B inclusive.
Constraints
T<=100
1<=A<=B<=10^50
Sample Input
3
121 4325
432 4356
4234 4325667
Sample Output
60
58
207159
hide comments
|
sajalhawk:
2018-07-29 21:51:37
I am using Python 3 and the following method to initialise the list : dp = [[[[-1 for l in range(60)]for k in range(60)] for j in range(60)] for i in range(51)]. But it is taking a long time to execute. Please suggest any alternative |
|
sxie12:
2018-02-13 04:43:12
dp[51][18][18][18][2] TLE -> dp[51][36][36][2][2] AC
|
|
siddiboy:
2017-06-01 22:17:51
1 10^50
|
|
datbeohbbh:
2017-05-22 06:22:56
finally AC,silly mistake |
|
kr1996:
2016-06-23 22:49:15
1 -> 10^50 : 129112454 |
|
kejriwal:
2016-01-24 18:38:34
Awesome Problem :') |
|
naruto09:
2016-01-21 22:03:24
still cant figure out why i am getting WA...-_- |
|
ashish kumar:
2016-01-18 18:18:30
finally accepted |
|
Vu Duy Truc:
2015-11-12 09:09:47
Please give me some testcase ???
|
|
elita lobo:
2015-08-08 13:39:34
@Saransh Bansal, Can you please check my code and tell me why I am getting wa? id- 14848296 |
| Added by: | Saransh Bansal |
| Date: | 2012-03-21 |
| Time limit: | 0.391s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
RSS