ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1017. Staircases

I can't understand why I got Wrong Answer?
Posted by Нфиє 12 Apr 2003 05:10
I can't understand why I got Wrong Answer?
I use a DP method,and I am afraid that I got wrong answer here.

Here's my program:

#include<iostream.h>
#define MAX 500

void read();
void work();
void write();

long n,f[MAX+1][MAX+1];

int main()
{
    read();
    work();
    write();
    return 0;
}

void read()
{
    cin>>n;
}

void work()
{
    unsigned int k,m,i,j;
    f[0][0]=1;
    k=n;
    for (m=1;m<n;m++)
        {
            for (i=m;i<=n;i++)
            {
                for (j=k;j>0;j--)
                {
                    f[i][j]+=f[i-m][j-1];
                }
            }
        }
    f[n][n]=1;
}

void write()
{
    unsigned long total,i;
  total=0;
    for (i=1;i<=n;i++)
    {
        total+=f[n][i];
    }
  cout<<total<<endl;
}

Thank you!
Because insigned long is not enough (-)
Posted by Dmitry 'Diman_YES' Kovalioff 12 Apr 2003 17:21
Why is your program so long?
Posted by XmYjd 16 Nov 2006 13:36
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.