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
|
pranay_garg:
2019-10-10 14:50:51
How does it work if we initialize dp[] only once before test cases??
|
|
sahilshelangia:
2019-10-10 13:41:06
Last edit: 2019-10-10 13:41:31 |
|
zephyr_96:
2019-10-08 10:11:11
dp[51][55][55][55] gets TLE in java but AC in C++. |
|
quanpham0805:
2019-06-01 18:55:44
nhật hào bẩn
|
|
tranminhkhang7:
2019-05-22 10:47:50
Last edit: 2019-05-22 10:49:36 |
|
tototete:
2019-05-22 08:17:19
trâu cũng AC |
|
zingme123aptx:
2019-05-20 10:55:18
trâu cũng AC |
|
harshit2202:
2019-03-22 13:47:35
We should fill(dp,-1) in every test case. but this will give TLE.
|
|
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 |
| 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