Stacking Pancakes

Problem code: PANSTACK

All submissions for this problem are available.

Chef is good at making pancakes. Generally he gets requests to serve N pancakes at once. He serves them in the form of a stack. A pancake can be treated as a circular disk with some radius.

Chef needs to take care that when he places a pancake on the top of the stack the radius of the pancake should not exceed the radius of the largest pancake in the stack by more than 1. Additionally all radii should be positive integers, and the bottom most pancake should have its radius as 1. Chef wants you to find out in how many ways can he create a stack containing N pancakes.

Input

First line of the input contains T (T <= 1000) denoting the number of test cases.

T lines follow each containing a single integer N (1 <= N <= 1000) denoting the size of the required stack.

Output

For each case the output should be a single integer representing the number of ways a stack of size N can be created. As the answer can be large print it modulo 1000000007.

Example

Input

2
1
2

Output

1
2
Author: kaushik_iska
Tester: laycurse
Editorial http://discuss.codechef.com/problems/PANSTACK
Date Added: 1-03-2012
Time Limit: 1 sec
Source Limit: 5000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Size of pancakes vary from 1

kartik_a91 @ 1 Apr 2012 03:22 PM
Size of pancakes vary from 1 to N all the time ??

can anyone explain this

hariprasath @ 1 Apr 2012 03:45 PM
can anyone explain this problem clearly:(

can anyone explain the test

almighty @ 1 Apr 2012 03:47 PM
can anyone explain the test cases please ??

what are the pancakes radii

cyberax @ 1 Apr 2012 05:19 PM
what are the pancakes radii ???

the radii of the first

migdal @ 1 Apr 2012 05:40 PM
the radii of the first pancake is 1,after that figure it out from problem statement what all radii can be there for subsequent pancakes

@migdal suppose the radii

nitish712 @ 1 Apr 2012 06:26 PM
@migdal suppose the radii are say 1,2,3,..... then how can u explain the possibilities for 2 pancakes

@nitish712: In the case of

kaush_adm @ 1 Apr 2012 07:25 PM
@nitish712: In the case of making 2 pancakes, the possible solutions are: (1, 2) and (1, 1). Please read the problem statement, you will notice that a pancake of radius 3 is not possible for the case of making 2 pancakes.

Please dont discuss

kaush_adm @ 1 Apr 2012 09:04 PM
Please dont discuss strategy/answers for questions.

@Kaush_adm: Can you please

aigoruan @ 2 Apr 2012 11:10 AM
@Kaush_adm: Can you please explain the possibilities for 3 pancakes?

Can anybody explain the

amitsam92 @ 2 Apr 2012 03:35 PM
Can anybody explain the reason for runtime error in python

whats answer for 3

architmittal @ 2 Apr 2012 04:28 PM
whats answer for 3 pancakes????

While the problems here are

shikhin @ 2 Apr 2012 05:37 PM
While the problems here are good, I think I'm not liking the way the examples are presented. Give two test cases, 1 and 2, with answers 1 and 2.. isn't actually helpful for validating your try at it. If perhaps someone could edit this problem with better test cases, I'd be happy. Otherwise, I believe, I'd need to try whatever I cooked up.

@Admin please provide non

swissknife007 @ 2 Apr 2012 08:39 PM
@Admin please provide non -trivial test cases as in this case,one can't check the answer by hand or any calculator.

the test cases given are of

amrendrakumar @ 2 Apr 2012 09:10 PM
the test cases given are of no use really. @Admin provide us a test case for a large input N, else whats the point in giving the test cases.....

Here is the explanation for

kaush_adm @ 2 Apr 2012 09:12 PM
Here is the explanation for 3: (1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 2) (1, 2, 3) answer for 3 is 5.

@Admin could you please give

amrendrakumar @ 2 Apr 2012 09:22 PM
@Admin could you please give just one answer for a large N in range 500 to 1000 ??

admin gettin a wrong answer

y2kcoders @ 2 Apr 2012 10:56 PM
admin gettin a wrong answer in python while all my test cases are right! plz give d value for n=1000 wil help in a lot of debugging! Thanks!!!

@admin I tried using python,

rohanag @ 2 Apr 2012 10:57 PM
@admin I tried using python, got TLE although the code was working fine on my system, Then I implemented the same logic in cpp, and it executed in .28 second............. whats wrong with the python code http://www.codechef.com/viewsolution/946193

@admin For N=6, 1 2 3 4 5 1

mehankit7 @ 2 Apr 2012 11:27 PM
@admin For N=6, 1 2 3 4 5 1 is valid right?

very nice problem..

Manoharprabhu @ 2 Apr 2012 11:31 PM
very nice problem..

My test are timing out

karora @ 3 Apr 2012 12:18 AM
My test are timing out despite of getting executed in .40 sec on ideone for worst case scenario. 1000 repeated thousand times. Can admin help me with it. May I know the time limits. I am using C if that helps

@mehankit7: Yes.

kaush_adm @ 3 Apr 2012 09:07 AM
@mehankit7: Yes.

Good ques. :) Doing a very

shek8034 @ 3 Apr 2012 12:06 PM
Good ques. :) Doing a very silly mistake. Getting TLE again n again, cost me 5 submissions !!!!

@Kaush_adm "Chef needs to

fox_3 @ 3 Apr 2012 02:29 PM
@Kaush_adm "Chef needs to take care that when he places a pancake on the top of the stack the radius of the pancake should not exceed the radius of the largest pancake in the stack by more than 1." Here is the explanation for 3: (1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 2) (1, 2, 3) answer for 3 is 5. how (1,2,1) is a solution? plz reply..!!!!!plz plz plz...!!!

i got runtime error.....which

chaubey12 @ 3 Apr 2012 08:46 PM
i got runtime error.....which data type i have to use for this??

@fox_3 because its given more

nitish712 @ 3 Apr 2012 08:58 PM
@fox_3 because its given more than 1 and not more than or equal to 1.... :D thats it!!!

@admin python giving NZEC

divyagupta @ 4 Apr 2012 02:12 AM
@admin python giving NZEC error ...??

in my pc its working but in

sukusuku @ 4 Apr 2012 04:15 PM
in my pc its working but in code chef its showing run time error plz tell me the reason 953650 this is my submission

my code is running in good

abhisht7 @ 4 Apr 2012 05:35 PM
my code is running in good time in ideone but everytime it gives TLE here?? i am coding in java.

Please, don't post any test

sergey_adm @ 4 Apr 2012 08:44 PM
Please, don't post any test cases here. Clarifying the statement is OK but giving any tips (like for N=X the answer is Y) is restricted by the rules.

@kaush_adm: Sir, for n = 3,

bilbo_dhawal @ 4 Apr 2012 10:19 PM
@kaush_adm: Sir, for n = 3, why is (1, 3, 2) not valid ? disk of bottom-most radius is 1. top-most disk's radius (2) is lesser and does not exceed max-radius disk (3) by 1

@bilbo_dhawal: (1,3,2) is not

poojits @ 4 Apr 2012 10:52 PM
@bilbo_dhawal: (1,3,2) is not valid. Start with 1 on top of the stack. Now you cant put 3 on top of the stack as it is more than 1+max which is 1+1 currently.

@poojits: ah yes ... stupid

bilbo_dhawal @ 4 Apr 2012 10:54 PM
@poojits: ah yes ... stupid of me not to notice that .. thanks :)

this is TLE in O(n)?! are you

rjjfdn @ 5 Apr 2012 12:32 AM
this is TLE in O(n)?! are you serious?@_@ I think my code really runs very well, and I think I am using the right trick here. I am coding in java. @abhisht7 i feel you. really

@admin- will you clarify what

abhisht7 @ 5 Apr 2012 01:43 AM
@admin- will you clarify what exactly 1s time constraint mean? for how many test cases should the code take 1s to run?? or all 1000 cases will be checked and total time be calculated?

I think abhisht7 has a point

swissknife007 @ 5 Apr 2012 03:24 AM
I think abhisht7 has a point

in my pc its working but in

sukusuku @ 5 Apr 2012 09:48 AM
in my pc its working but in code chef its showing run time error plz tell me the reason 953650 this is my submission please reply me i am posting this for second time

@admin pls provide some test

rohith_seel @ 6 Apr 2012 03:33 PM
@admin pls provide some test cases where my code is going wrong

how funny, someone asking for

jehad @ 6 Apr 2012 04:55 PM
how funny, someone asking for test cases before ending of contest

whats the output for n=5??

assasin143 @ 6 Apr 2012 05:08 PM
whats the output for n=5??

@assasin143: why you cannot

betlista @ 6 Apr 2012 05:52 PM
@assasin143: why you cannot generate all _valid_ stacks and count them for n = 5?

for n=5 (1,2,3,4,5)

mmanoj001 @ 6 Apr 2012 08:34 PM
for n=5 (1,2,3,4,5) (1,2,3,4,1),(1,1,1,1,1).......(1,2,3,4,4) ... just read all discussion then you will get it easily..

is possible combinations are

khadarbasha @ 7 Apr 2012 01:01 AM
is possible combinations are 14 for N=4?

wats d ans for n=1000 ??

melwin_jose @ 7 Apr 2012 01:18 AM
wats d ans for n=1000 ?? getting time limit error here, just wanted 2 check if my algo is ryt

Is answer for 1000 is

vikram535 @ 7 Apr 2012 10:49 AM
Is answer for 1000 is 110961515?

@vikram535 : yes thats wat i

melwin_jose @ 7 Apr 2012 11:24 AM
@vikram535 : yes thats wat i got for n=1000, but still getting wrong answer :(

@melwin_jose: me too :( Can

vikram535 @ 7 Apr 2012 11:36 AM
@melwin_jose: me too :( Can anybody give a test case result for a large number?

@vikram535: same here and

deswal161990 @ 7 Apr 2012 12:30 PM
@vikram535: same here and getting WA

Can any one clear what is the

include @ 7 Apr 2012 02:04 PM
Can any one clear what is the result for n=4 and n=5. Plz @admin give some hint. for n=8: (1,2,3,4,5,6,4,1) is it a valid sequence or not? plz plz plz any body help ?

@include: i don't think

dispareil @ 7 Apr 2012 02:25 PM
@include: i don't think (1,2,3,4,5,6,4,1) is a valid sequence for n=8 bcoz radius of last pancake in the stack is 1 and the highest radius in the stack is 6...so acc. to ques. the radius of the pancake on the top of the stack should not exceed the radius of the largest pancake in the stack by more than 1

12345641 is a valid sequence

shashank1992 @ 7 Apr 2012 05:02 PM
12345641 is a valid sequence because the question says radius cannot exceed the largest one but it can always be less by anything.

@ADMIN.."Can any one clear

fox_3 @ 7 Apr 2012 05:45 PM
@ADMIN.."Can any one clear what is the result for n=4 and n=5. Plz @admin give some hint. for n=8: (1,2,3,4,5,6,4,1) is it a valid sequence or not?"........ plz comment on this ... plz plz..:) :) :)

@fox_3 : Valid

cool123 @ 7 Apr 2012 08:18 PM
@fox_3 : Valid

Codechef beginning to suck

cupidvogel @ 7 Apr 2012 09:50 PM
Codechef beginning to suck these days. What is the meaning of sample test case if all it does is printing out the output for trivial inputs like 0 and 1? This doesn't make the test any more tough, it only sucks more. Look at the test cases provided in Topcoder or Codejam contests, and then look at the test cases provided here...

for n=4 output is 14 is it

khadarbasha @ 7 Apr 2012 09:50 PM
for n=4 output is 14 is it correct?plz comment on this..

Can a smaller pancake be

cupidvogel @ 7 Apr 2012 09:53 PM
Can a smaller pancake be placed on top of a larger pancake? That is, can I put a pancake of radius 2 atop a pancake of radius 3?

@cupidvogel: the sample test

satya_patel @ 7 Apr 2012 10:05 PM
@cupidvogel: the sample test cases given for testing your input/output format... ...............not for your solution.............don't expect any hint for solution from sample cases................its only for testing your solution against input/output...................and your 2nd Q yes you can put any smaller radius pancake on the larger pancake.....................!!!

"when he places a pancake on

truegff @ 7 Apr 2012 10:24 PM
"when he places a pancake on the top of the stack the radius of the pancake should not exceed the radius of the largest pancake in the stack by more than 1." so {1213} case is legal, because before Chef placed pancake with radius 3 on the top, largest pancake had radius 2. Am I right?

@truegff yeah

satya_patel @ 7 Apr 2012 10:49 PM
@truegff yeah right..............!!!

@satya_patel thanks,

truegff @ 7 Apr 2012 10:52 PM
@satya_patel thanks, progression now comes clear

@Satya Patel, My point,

cupidvogel @ 8 Apr 2012 12:22 AM
@Satya Patel, My point, exactly. The sample test cases are supposed to stand you in some stead at least, regarding your solution. Everyone knows the answers to the trivial test cases like 0 and 1, then why give them?

@cupidvogel

satya_patel @ 8 Apr 2012 12:33 AM
@cupidvogel ....................yeah you are right...................giving any trivial case may leak some information about the solution which is not correct in competition.......................and for the limits for your solution there is constraints so you can figure out..................!!!

What I've figured out is: one

truegff @ 8 Apr 2012 12:45 AM
What I've figured out is: one shouldn't depend on comments. I've lost a lot of time following wrong input output samples posted in comments. Unfortunately my knowledge of english doesn't let me easily cut into the problem statement and understand it for the first time, then I see comments written with simplier words (please don't receive as offence), and I start building a solution mostly based on comments. That's a big time-eating mistake, thats what I've figured out.

khadarbasha n=14 answer is 15

jini123456 @ 9 Apr 2012 03:08 PM
khadarbasha n=14 answer is 15

@Admin: I think there is some

bhuwan.chopra @ 9 Apr 2012 06:53 PM
@Admin: I think there is some mistake in judging the solutions. I am getting TLE repeatedly. But the same program runs under 0.4 secs for max case possible (1000 test cases). Also, I get response in much lesser time than 5 secs whereas i can see Java programs accepted with more than 5 secs.

@all:those who r gettin wrong

anubhawraj @ 9 Apr 2012 11:38 PM
@all:those who r gettin wrong answer,jst submit your code twice.....same code i have submitted twice in first chance it was WA and chance got accepted:)

Does Python on my laptop

naagii @ 11 Apr 2012 01:41 PM
Does Python on my laptop works faster than CodeChef python3 compiler? I'm getting TLE :D

getting wrong answer... my

mohitgoel @ 11 Apr 2012 01:55 PM
getting wrong answer... my answer for 1000 is same as what others posted in comment... not sure what to do

@mohitgoel Check the this

naagii @ 11 Apr 2012 02:11 PM
@mohitgoel Check the this comment form truegff post="...{1213} case is legal..."

SUCCESSFUL SUBMISSIONS


Fetching successful submissions