NUMTSN - 369 Numbers
A number is said to be a 369 number if:
- The count of 3s is equal to the count of 6s and the count of 6s is equal to the 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 ≤ 1050
Example
Input: 3 121 4325 432 4356 4234 4325667 Output: 60 58 207159
hide comments
|
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
|
|
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 |
|
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
|
| Added by: | Saransh Bansal |
| Date: | 2012-03-21 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
RSS