really smart!
how can you get that dude?

Hello,

Thank you for your hint, it was very useful for me

 and yes, your solution is awesome!

really nice idea, i like it.

good job, man

But how does this transition ensures that the next column always has more bricks than the current column?

Ha!
My solution: only 0.001 sec and 70 Kb!
And it's normal solution (no cheating).
I sent it some minutes ago.

PS: It's very good that your solution works fast but
    Always there is better one :)

my solution is O(0) :)

Use bottom-up approach, calling function and return rakes huge amount of time

Let's start from the beginning:
Let R(n) will be the function that returns count of unique staircases.
Now let's introduce function G(n,j) that returns count of unique staircases each first step of which has more than j bricks.
Then R(n) = G(n,0) - 1 . We have to subtract one because it is the case when all bricks are spent on the first step.

G(n,j) = (n>j ? 1 : 0) + (G(n-j-1, j+1) + G(n-j-2, j+2) + ... +G(0,n))

G(n,j-1) - G(n,j) = (n == j ? 1 : 0) + G(n-j, j) => G(n,j) = G(n,j-1) - G(n-j,j) - (n == j ? 1 : 0)

We know that in the case when n<=j G(n,j) = 0, so we can solve upper equation only for cases when j<n, in such cases upper formula will transform to G(n,j) = G(n,j-1) - G(n-j,j).

But we still have to solve the cases when j == 0 and i > j as G(n, 0) = 1 + G(n-1, 1) + G(n-2, 2) + ... + G(0,n)

//Alloc and init matrix g with zeroes

//Calculat g matrix
for(i = 2; i<=N; ++i){
    g[i][0] = 1;
    for(j=1; j<i;++j){
        g[i][0] += g[i-j, j];
    }
    for(j=1; j<i;++j){
        g[i][j] = g[i][j-1] - g[i-j,j];
    }
}
cout<<g[N][0]-1;

Edited by author 09.02.2020 17:14

You are printing a, print(a).  A is a LIST.

It is compressed 2-dimensional dynamic programming state.
It is like we take staircase from 1,2,...,N cubes and add one more step.
Subtract one to not count zero len staircase.

Edited by author 08.07.2017 16:20

"Compressed " means that say dp[x] = Sum(dp[x] [i]) {i = 0,1,...,N}

Edited by author 08.07.2017 16:20

Edited by author 08.07.2017 16:22

I got WA #7 as well.. not sure what went wrong anyone has the input n and expected output? Thanks

can u help me with some algorithm better than dp(which works in O(n^2))

Edited by author 11.07.2016 03:57

i used unsigned but didn't get any wrong answer

So am I.. But sometimes I am trying to calculate how many new figures give us each of them for any N.
I don't know is it correct or is it the easiest way, but it sometimes works)

It's allright!
You cannot have two neighbour stair steps with horizontal difference more than 1.

7

> const n=500;
> var a:array[1..n]of string;
>     i,j,k,l,m,rk,v,t,z,pus:longint;
>     sum,ss,zz:string;
> function mmm(p:longint):longint;
>   begin
>   v:=1;
>     while ((v+1)*(v+2)) div 2<=p do v:=v+1;
>   mmm:=v;
>   end;
> function plus(pluss1,pluss2:string):string; {only pozitive!!!}
>   var plusi,pluscode,plusi1,plusi2,plusna,plusba:integer;
>       pluss,plusss:string;
>   begin
>     if pluss1='' then pluss1:='0';
>     if pluss2='' then pluss2:='0';
>   pluss:='';
>     while length(pluss1)<length(pluss2) do pluss1:='0'+pluss1;
>     while length(pluss2)<length(pluss1) do pluss2:='0'+pluss2;
>   plusna:=0; plusba:=0;
>     for plusi:=length(pluss1) downto 1 do begin
>     val(pluss1[plusi],plusi1,pluscode);
>     val(pluss2[plusi],plusi2,pluscode);
>     plusba:=(plusi1+plusi2+plusna) mod 10;
>     plusna:=(plusi1+plusi2+plusna) div 10;
>     str(plusba,plusss);
>     pluss:=plusss+pluss;
>     end;
>     if plusna<>0 then begin
>     str(plusna,plusss);
>     pluss:=plusss+pluss;
>     end;
>   plus:=pluss;
>   end;
> begin
>   readln(m);
>     for i:=1 to m do a[i]:='1';
>   sum:='0';
>   rk:=mmm(m);
>     for i:=2 to rk do begin {&#1031;&#1168;&#1072;&#1168;&#1038;&#174;&#1072; &#1031;&#174; k}
>       for j:=1 to i do begin
>       t:=i+j;
>         while (t<(i+1)*i div 2)and(t<=m) do t:=t+i;
>       ss:='0';
>         while t<=m do begin
>         zz:=a[t];
>         a[t]:=plus(a[t-i],ss);
>         t:=t+i;
>         ss:=zz;
>         end;
>       end;
>       if m<((i+1)*i div 2)-1 then pus:=m else pus:=((i+1)*i div 2)-
1;
>       for z:=1 to pus do a[z]:='0';
>     sum:=plus(sum,a[m]);
>     end;
>   writeln(sum);
> end.

your solution is verry stupid. I think only one lamer could solve
the problem like this. I wrote only 22 lines. Of course, Pascal suks.

what does your program mean?

program ural1017;
var
  q:array[0..500]of int64;
  n,i,j:integer;
begin
  fillchar(q,sizeof(q),0);
  readln(n);
  q[0]:=1;
  for i:=1 to n do
    for j:=n downto i do
      inc(q[j],q[j-i]);
  writeln(q[n]-1);
end.

haha, why anyone use array with length 500?
just try to think a little, program need array with length no more 32!

LOL! the only lamer here is  "Yuriy Frolov (ufrolov@ukr.net)"-:D :D :D Your program is worst i've ever seen :D :D :D You chose stupidest way to solve and  you think that others are lamers??? :D it would be better to hide this solution except to submit it :D