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
Piyush Kumar:
2015-06-02 20:37:17
Python , thou art beautiful. |
|
eightnoteight:
2014-12-30 12:22:15
excellent dp problem |
|
Bharath Reddy:
2014-09-28 08:25:00
Check for N=0.. |
|
TIGM:
2014-09-26 21:18:18
good one
|
|
Ouditchya Sinha:
2013-09-06 17:23:24
@rishabh singh : Congratulations!! :) |
|
Rishabh singh:
2013-09-06 07:31:47
after 40 attempts a/c the best solution in C!!! |
|
Rishabh singh:
2013-08-24 20:53:31
My sub. id:9906185 ....I have solved this question in C,i have matched every bit of output with that of my friend whose solution is accepted..... for no. of digits 1 to 10000 the output txt file is of 8.28 MB (8,692,608 bytes)..run time is .32 sec..still the solution is not accepted!!please check.... |
|
Amitayush Thakur:
2013-08-15 18:59:02
Easy one using DP ;) |
|
Vikas Kushwaha:
2012-12-16 13:46:44
good problem..
|
|
shubham gupta:
2012-08-10 22:21:43
in c++ even unsigned long long int is not working . should i use string or is there any other way to add numbers.
|
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 |