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
|
iceelement:
2019-01-25 07:09:23
It will TLE if you keep counts of all numbers, or even if you keep counts/3, keep [cnt6-cnt3] and [cnt9-cnt6], also optimize based on the fact that the difference can't be outside [-17,+17]. TLE's if you do the [0,r] - [0,l-1] type of digit dp which uses single flag, use [l,r] type dp which uses 2 flags instead. AC in 0.37 seconds in CPP14 after these optimizations. |
|
bruzelee:
2018-12-17 02:16:08
iam getting WA, donno why Last edit: 2018-12-17 02:29:56 |
|
cichipi_:
2018-12-13 06:26:47
[[F-word edited]]...Time limit: 0.391s .... dp[2][17][17][17][51] gets TLE (-_-)
|
|
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...-_- |
| 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