MYQ3 - The Dating Dress Problem
Gauthami has to get dressed for a date. She is going to meet Prasanna in the poshest restaurant in the country of Thuvax.
Prasanna arrives early and sees the outfit she has picked.
While waiting outside, Prasanna being a restless nerd calculates the number of ways she can get dressed.
The complete outfit she picks is represented as a string of digits. The digits represent the following details about the apparel:
(apparel = clothing or accessories or any other part of the outfit)
1 - a 2 piece apparel where first piece has to be worn before the other. It is followed by the description of the two pieces in order.
2 - a 2 piece apparel which can be worn in any order, and it is not necessary to complete one apparel before starting another one. It is followed by the description of the two pieces in order.
0 - a single piece of apparel which can be put on directly.
Help Prasanna calculate the number of ways in which Gautami can get dressed. Since Prasanna does not want to make Gauthami bored by telling her a huge number, he wants to tell her the number of ways modulo 1000000007.
For example, consider an outfit comprising of a shirt, a skirt into which the shirt has to be tucked in and
a neck cloth worn over the shirt.
It will be represented as 10200 and the number of ways she can get dressed is 2(She has to wear the shirt first after which she can wear either the skirt after the neck cloth or neck cloth after the skirt).
Input
First line is a positive integer T (T<=100) representing the number of testcases
It is followed by T lines, each containing a string S of digits (each digit will be one of 0,1,2) describing the outfit, 1<=|S|<=100,000
The complete outfit comprises of a single item.
Output
Output for each test case should consist of one line representing the number of ways in which Gauthami can get dressed modulo 1000000007.
Example
Input: 3
10200
0
1102000 Output: 2
1
2
hide comments
Daga:
2014-08-09 09:09:20
getting tle with O(n) complexity....any solutions
|
|
Daniel Ampuero:
2012-03-10 06:56:01
What would be the output for the input string 2220020020200? |
|
Mitch Schwartz:
2012-02-29 11:15:11
Hmm, I think the rules are not so clear. For example consider 2200200. This could correspond to: a pair of gloves and a pair of socks. Now, can she put on first one sock, then one glove, then the other sock, then the other glove? Or must she complete one pair before starting the other?
|
Added by: | jack(chakradarraju) |
Date: | 2012-02-14 |
Time limit: | 1s-1.614s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Bytecode 2012 |