ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1017. Лестницы

Something with tests?
Послано Aracon 26 май 2007 20:12
It looks strange.
I get WA on test 6.
I thought it is a bug in algorithm. To test my program I copied solution from this forum and printed all answers in file. All answers of my program have been compared with generated ones. They are equal.
What is the cause of WA?

PS My program (both solve1 and solve_true get WA):

#include <stdio.h>
#include <string.h>

int n;
long long tb[505][505];


long long solve1(int n) {
    int i,j,k;
    for(i=0; i<505; i++)
        for(j=0; j<505; j++)
            tb[i][j]=0;

    tb[0][0]=1;
    tb[1][1]=1;
    for(j=2; j<=n; j++) {
        for(i=j; i<=500; i++) {
            for(k=j-1; k>=0; k--) {
                tb[i][j]+=tb[i-j][k];
            }
        }
    }
    tb[n][n]=1;

    long long res=0;

    for(i=0; i<=n; i++) {
        res=res+tb[n][i];
    }
    res=res-1;
    return res;
}
long long solve_true(long long n) {
    int i,j,k;
    for(i=0; i<505; i++)
        for(j=0; j<505; j++)
            tb[i][j]=0;

    tb[0][0]=1;

    for(j=1; j<=n; j++) {
        for(i=n; i>=j; i--) {
            tb[0][i]=tb[0][i]+tb[0][i-j];
        }
    }

    return tb[0][n]-1;

}

int main(int argc, char* argv[]) {

#ifndef ONLINE_JUDGE
    FILE* fin=fopen("input.txt", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
#else
    scanf("%d", &n);
#endif
    printf("%lld", solve1(n));
    return 0;
}