SPOJ.com - Problem NUMTSN

NUMTSN - 369 Numbers

no tags

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

121 4325

432 4356

4234 4325667

Sample Output

207159

Submit solution!

hide comments

< Previous 1 2 3 Next >

	harshit2202: 2019-03-22 13:47:35 We should fill(dp,-1) in every test case. but this will give TLE. How to avoid that.? dp[50][2][17][17][17].
	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 (-_-) dp[2][17][17][17][51] will get AC (^_^) if you do Fill(dp,-1) exactly once before entering TestCase loop. But , it will give u WA if u don't change.....??? Last edit: 2018-12-13 16:22:27
	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 Also try to minimize the number of operations per state.
	siddiboy: 2017-06-01 22:17:51 1 10^50 ans=129112453
	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 :')

Submit solution!

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