ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1017. Staircases

Do you know a faster algorithm?
Posted by lql1993 23 Oct 2008 19:18
I used dp and this is my program:
var f:array[0..500,0..500]of extended;
i,j,n:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;
begin
fillchar(f,sizeof(f),0);
f[0,0]:=1;
for i:=1 to n do
for j:=1 to i do
f[i,j]:=f[i,j-1]+f[i-j,min(j-1,i-j)];
writeln(f[n,n]:0:0);
end.

But I want to know a faster algorithm,
Re: Do you know a faster algorithm?
Posted by Antagonism 1 Feb 2011 15:10
let us suppose this is a building.
T[i][j] is the total number of buildings which uses i bricks, and its ground floor is exactly j.
O(n*logn).
AC code.
#include<iostream>
using namespace std;
__int64 T[501][35];
__int64 sum;
int n;
inline __int64 max(__int64 i,__int64 j)
{
return i>j?i:j;
}
int main()
{
int i,j,k;
scanf("%d",&n);
T[1][1]=1;
for(i=2;i<=n;i++)
{
for(j=1;((j*(j+1))>>1)<=i;j++)
{
T[i][j]=T[i-j][j]+T[i-j][j-1];
}
}
for(j=1;((j*(j+1))>>1)<=n;j++)
{
sum+=T[n][j];
}
printf("%I64d\n",sum-1);
return 0;
}
Re: Do you know a faster algorithm?
Posted by Antagonism 1 Feb 2011 15:20
sorry it's O(n^3/2)