NUMPLAY - Fun with numbers
Consider a set of 4 numbers {1, 3, 5, 7}. Form a number using these digits in the set under the following constraints,1 can be followed only by 3 (i.e. the number may contain 13 but not 15 or 17 or 11 eg:13573 is valid but not 113573), 3 can be followed only by 1 and 5, 5 can be followed only by 7, 7 can be followed only by 5 and 3.
Find the number of such numbers of length n.
e.g.: 37, 51, 53, 71 are all not a valid number of length 2. 131 is a valid number of length 3. 1357 and 1313 are all a valid number of length 4 but 11 or 1537 or 15 or 17 or 33 are not valid numbers.
Input
t, First line of input contains number of test cases 0 <= t <= 40.
Remaining t lines consist of length n for each test case 0 <= n <= 10000.
Output
Output the number of possible numbers of length n followed by a line (note long long int in C++ may not be sufficient.)
Example
Input: 3 2 1 4 Output: 6 4 13
Note: time limit is reduced for checking the accuracy.
hide comments
Ivan Hendrajaya:
2012-04-17 15:16:44
@B.R.ARVIND: Thanks, just follow my intuition. :) |
|
B.R.ARVIND:
2012-04-17 15:16:44
@Ivan Hendrajaya:superb solution :) |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-04-17 15:16:44
nice problem ;) |
|
noname:
2012-04-17 15:16:44
some more test cases please... |
|
B.R.ARVIND:
2012-04-17 15:16:44
@numerix: in such a case ,i have to rejudge everyone's solutions . |
|
numerix:
2012-04-17 15:16:44
@problemsetter: Thanks for answering and explanation. But why did you delete my comment? As you refer to that comment, it would have been better not to remove it.
|
|
B.R.ARVIND:
2012-04-17 15:16:44
@confused:dont get confused:P .look at the question, 37,51,53,71 are all NOT a valid number |
|
B.R.ARVIND:
2012-04-17 15:16:44
problem with all changes made |
|
B.R.ARVIND:
2012-04-17 15:16:44
@numerix:this changes were made because this is my first problem.no more such changes ll be made in future @santhana:how can there be a number of length 0 ? |
|
Santhana Krishnan:
2012-04-17 15:16:44
The test cases are expecting 0 as output for n=0. Should be 1 in my opinion. |
Added by: | B.R.ARVIND |
Date: | 2012-04-03 |
Time limit: | 1s |
Source limit: | 30000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |