SPOJ.com - Problem AMZRCK

AMZRCK - Amz Rock

no tags

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 is the number of test cases.

Each test case 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?

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 Next >

	Shashank Tiwari: 2015-12-12 19:03:07 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
	prakash_reddy: 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
	Abhinandan Agarwal: 2015-08-27 19:51:29 Remove spoilers ..
	Babu: 2015-08-18 11:18:54 real life implementation of fibo !! thanks @Himanshu and @pika_pika
	anuveshkothari: 2015-08-09 15:55:29 @piyush comment helps.. simple dp with pre-computation..
	Piyush Kumar: 2015-06-14 16:31:22 If it is of any help , n (number of tracks) is less than 45. :) Last edit: 2015-06-14 16:32:28
	[Mayank Pratap]: 2015-05-24 04:42:55 Good problem for newbies like me!!!
	Maroof: 2015-05-14 08:51:51 Don't use dynamic array in C++ :p it gives error
	Sahil Dua: 2014-10-24 11:18:01 0.00 AC with easy DP. Can be solved without DP as well with minimal pre-processing done.
	ayush: 2014-06-05 09:41:36 elegant but don't read the comments they give it away

Submit solution!

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 )