SPOJ.com - Problem STRCOUNT

STRCOUNT - Counting binary strings

Let f(n, k) is the number of length n binary strings for which the length of the longest substring of ones is equal to k. You have to build a table of these values.

Input

None.

Output

63 lines - the n-th of them consists of n+1 values: f(n, 0) f(n, 1) ... f(n, n).

Example

Submit solution!

Added by:	czylabsonasa
Date:	2011-09-20
Time limit:	0.102s
Source limit:	3333B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	folklore

hide comments

2011-10-20 11:09:07 Sidharth Gupta
@Noszály Csaba: I am getting WA repeatedly. I have cross checked each value for n=1 to n=16 from brute force code and for higher values i have checked whether they sum up to power of 2 or not. can't figure out why WA.. can you help me out? submission id: 5870244.

Edit: AC. Had problem with array bounds, so WA on spoj.

Last edit: 2011-10-20 19:52:24

2011-10-19 01:48:27 sharad
dont use double long long is enough

Last edit: 2011-10-20 11:02:13

2012-08-28 17:07:50 Paused ||
blashyrkh is absolutely right !

2011-09-23 06:33:40 RAJDEEP GUPTA
@Noszály Csaba: I am getting WA. Can you kindly check why I am getting WA??
My submission id is: 5709944
Please reply!!!

>>> most of your output is wrong, eg. for n=5:
1 12 10 6 2 1
instead of
1 12 11 5 2 1
as zukow said inf times, you should write a brute force checker...

>>> Yes. My mistake.. I will keep your words in my mind.. And thanks a lot for replying and guiding..

>>>Atlast AC :) Thanks Noszály Csaba.

Last edit: 2011-09-25 12:21:44

2011-09-21 21:05:32 blashyrkh
You are not asked to get ONE f(n, m).
Think dynamically :)

2011-09-21 20:11:06 xiaodao
... How to get one f(n, m) quickly ?.. )