program staircases;
 var a:array[0..500] of extended;
     n,i,j:longint;
 begin
  read(n);
  fillchar(a,sizeof(a),0); a[0]:=1;
  for j:=1 to n do
    for i:=n downto j do a[i]:=a[i]+a[i-j];
  a[n]:=a[n]-1;
  writeLn(a[n]:0:0);
end.

pls explain ur algorithm i.e. write down recurrent equation that it
use ...

What does F(n) mean in your programme?

Thank Nickolas.

I didn't see his carefully, just a look. To my surprise it is so short. Suddenly I found a good way to solve this problem -- When I got AC , I found it looks like his one very much...

We can get f(m,n) = f(m,n-1) + f(m-n,n-1) easily
(Sorry my English isn't good enough to explain what m & n are.)
Notice that f(...,n) is based on f(...,n-1)
Then, we can get a good program.

Time : O(n^2)
Memory : O(n)

Thanks!

email me: oberon at verba.com.ua

Oh,that is easy to understand!
In fact,it's multinomial multiplication,and I think it's just (1+x)*(1+x^2)*(1+x^3)...... Is that right?

I solved this problem another way... But your program is perfect... can you explain how did you invent it?

My solution is fast! valery@uni.lg.ua

Edited by author 03.04.2005 04:15