Submit | All submissions | Best solutions | Back to list |
AMZRCK - Amz Rock |
To many people in many cultures, music is an important part of their way of life.
AmzMohammad is a fan of rock music. and he have n rock tracks (labelled from 1 to n) now he wants to select a playlist.
in his opinion a good playlist is one that have no two successive tracks.
in how many ways?
Input
first line = number of test cases
each testcase in an integer n(number of tracks)
Output
Output number of good playlists he can make.
answer is less than 1000000000. it is the only constraint :)
Example
Input: 2 1 2 Output: 2 3
note: a good play list may consist 0 track :)
note 2: how many Persian rock tracks we have?
Added by: | mohammad mahmoodi |
Date: | 2012-08-01 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GAWK BASH CSHARP GO ICON ICK WHITESPACE |
Resource: | AmzMohammad ( Mohammad Mahmoodi ) |
hide comments
|
|||||||||
2015-12-12 19:03:07 Shashank Tiwari
Question is bit unclear . Well , Question can be restated as : Given 'n' , we have a set of numbers {1,2,3 ,..... ,n} . we need to find count of all possible subsets of it such that no 2 consecutive number appears in any of the subsets. Empty set is allowed. ex : if n=3 , we have {1,2,3}. Possible sets are {} , {1}, {2} ,{3} ,{1,3}. Hence count = 5. Note that {1,2} or {2,3} are not allowed as they are consecutive. Also, It comes out that 1<=n <= 42 for this question. Last edit: 2015-12-12 19:40:54 |
|||||||||
2015-08-28 22:36:02
I assumed like this and got AC..... successive means it do not contain i and ith track... assume for n=3, say s1,s2,s3 are the tracks.... then possible ways are 0 s1,s3 s1 s2 s3 for n=4 s1,s2,s3,s4 are the tracks 0 s1 s2 s3 s4 s1,s3 s1,s4 s2,s4 Correct me if my assumption is wrong...:) Last edit: 2015-08-28 22:37:17 |
|||||||||
2015-08-27 19:51:29 Abhinandan Agarwal
Remove spoilers .. |
|||||||||
2015-08-18 11:18:54 Babu
real life implementation of fibo !! thanks @Himanshu and @pika_pika |
|||||||||
2015-08-09 15:55:29
@piyush comment helps.. simple dp with pre-computation.. |
|||||||||
2015-06-14 16:31:22 Piyush Kumar
If it is of any help , n (number of tracks) is less than 45. :) Last edit: 2015-06-14 16:32:28 |
|||||||||
2015-05-24 04:42:55 [Mayank Pratap]
Good problem for newbies like me!!! |
|||||||||
2015-05-14 08:51:51 Maroof
Don't use dynamic array in C++ :p it gives error |
|||||||||
2014-10-24 11:18:01 Sahil Dua
0.00 AC with easy DP. Can be solved without DP as well with minimal pre-processing done. |
|||||||||
2014-06-05 09:41:36 ayush
elegant but don't read the comments they give it away |