Lucky DrivingProblem code: LUKYDRIV |
All submissions for this problem are available.
"Nine is considered a good number in Chinese culture because it sounds the same as the word "long-lasting". Hence many
people want their car registration numbers to sum up to 9 on adding the digits recursively.
A car registration number can consist of 1,2,3 or 4 digits. Examples of some good car numbers are 63, 018, 9099, etc. whereas 12,129 are not good.
Why is 9099 good?
9+0+9+9 = 27
2+7 = 9
Similarly it is not difficult to see why 63, 018, 6669, 9999… are good."
Given a string of digits, print how many subsequences of the string result in good car registration numbers.
Note:
The zeros at the starting of the number are to be accounted for, i.e. 018 and 18 are different numbers.
Input
First line of the input contains T (T <= 200) denoting the number of test cases. T lines follow each containing a non-empty single string S. S contains only digits i.e. from [0-9]. Length of S <= 10000.
Output
For each case print how many subsequences of the string result in good car registration numbers. As the answer can be quite large print it modulo 1000000007.
Example
Input
2 10292 0189
Output
2 6
| Author: | kaushik_iska |
| Tester: | laycurse |
| Editorial | http://discuss.codechef.com/problems/LUKYDRIV |
| Date Added: | 21-04-2012 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
Can you clarify subsequences,
when you say "how many
Definition of "subsequences"
what if sequence has repeated
@ashshetty333, '90' is not a
I suspect he means pairwise
919 has to be 4, otherwise
Subsequences do not have to
@ashshetty333 909 is 6,not 4
in this 0189 their are six
Is '0' a valid car
@gaurav_singal: 081 is not a
@nihalpi1: '0' is valid but
2 Admins : is answer for "99"
@cupidon4uk: answer is 3, man
ans for 10292 is 2 by: "09,
@admin please look at this
@stalin u r not taking 189 &
So, the subsequences do not
The subsequences do not have
is there any change in
+1 to neil_812: getting
guys i'm getting the answer.
@remogoku if answer of the
@tornike4: thanks dude.. :)
@remogoku if x less than
what is the correct answer
for the string 999, should
is the answer for 666666:
the time limit is for all
I think the answer for 666666
@fahim_xubayer : u r wrong ..
@phantom11 -- can a car
@skauag333 : thank you very
@admin- WHEN WILL YOU
somebody,plz xlpain me how
@admin nevermind, I found the
@prasad_iiit : 09 ?? :P
@phantom11: I wonder is there
does S<=10000 means that S
@tyrant 116255
@tutum: You meant the answer
That's what I thought at
@neil_812: Thanks for the
Finally got AC, one stupid
2 sec. is time limit for 200
There are several the judge
@tyrant: could you please
@stalin: discussing algorithm
@tyrant: I got it! thnx :)..
what if sequence is 00099?
how to guarantee tha an
@admin: Is the subsequence
@admin... plz reply... i too
My algorithm performs less
My algo takes o(n) still time
finally Got Accepted
language partiality
Please reply
for the example input
what is the proper order for
@ravinder_singh , you forgot
i'm using long long int array
@mehrdad_ap : Same case with
@mng88 : however it's an
Time limit is too strict...my
AC at last.. Had to change
@admin: I am getting
@admin i m getiing
@admin:: i m also getting
@mehrdad_ap : I dont think
I am getting compilation
@yerzhanu: I have similar
my code is giving correct
0189 :-> 18, 81, 018, 108,
@bijupv: Have you tried
gOt acc
unistd.h ,....guys are using