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 1108. Heritage

Почему WA 1?
Posted by DarkSun1997 14 Jul 2017 16:01
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;



vector<long long > C(20000,0);
void mult(vector<long long> A,vector<long long> B)
{
    int d=0;
    for(int i=0;i<300;i++)
    {
        for(int j=0;j<300;j++)
        {
            C[i+j]+=B[i]*A[j];
            C[i+j+1]=C[i+j+1]+C[i+j]/100000000;
            C[i+j]=C[i+j]%100000000;
        }
    }
    C[0]++;
    for(int i=0;i<6000;i++)
    {
        C[i+1]=C[i+1]+C[i]/100000000;
        C[i]=C[i]%100000000;
    }
}
vector<long long> D(20000,0);
void mult1(vector<long long> A,vector<long long> B)
{
    int d=0;
    for(int i=0;i<300;i++)
    {
        for(int j=0;j<300;j++)
        {
            D[i+j]+=B[i]*A[j];
            D[i+j+1]=D[i+j+1]+D[i+j]/100000000;
            D[i+j]=D[i+j]%100000000;
        }
    }
    for(int i=0;i<6000;i++)
    {
        D[i+1]=D[i+1]+D[i]/100000000;
        D[i]=D[i]%100000000;
    }
}
void write(vector<long long> A)
{
    bool f=false;
    for(int i=9999;i>=0;i--)
    {
        if(A[i]!=0)
            f=true;
        if(f)
            cout<<A[i];
    }
    cout<<"\n";
}
int main()
{
#ifdef _DEBUG
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
#endif
    int n;
    cin>>n;

    vector<long long> A(10000,0);
    vector<long long> B(10000,0);
    A[0]=1;
    B[0]=1;
    for(int i=0;i<n;i++)
    {
        mult(A,B);
        mult1(A,B);
        for(int i=0;i<4000;i++)
        {
            B[i]=D[i];
        }
        for(int i=0;i<4000;i++)
        {
            A[i]=C[i];
        }
        for(int i=0;i<4000;i++)
        {
            C[i]=0;
            D[i]=0;
        }
        write(A);
    }
}

Вот код, скорее всего он не пройдет макс тест, но при запуске на первом тесте он выдает мне в студии ответ правильный, а тут нет
Re: Почему WA 1?
Posted by Mahilewets 14 Jul 2017 16:25
Потому что первый тест не совпадает с примером.
Попробуйте отправить программу,  которая выводит "2\n3\n" и вы убедитесь.
Re: Почему WA 1?
Posted by achpile 22 Jul 2017 13:42
ну у тебя и решение.... все ведь должно быть гораздо проще, хотя я тоже первый тест не могу пройти

#include <stdio.h>

long long int l;

int m(int i) {
    int res;

    if (i == 0) {
        l = 2;
        return 2;
    }

    res = l + 1;
    l *= res;
    return res;
}

int main() {
    int n, i, k;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        printf("%d\n", m(i));

    return 0;
}
Re: Почему WA 1?
Posted by Mahilewets 22 Jul 2017 15:04
По приколу,  я сдал задачу.
[code deleted]

Edited by moderator 08.04.2020 21:07
Re: Почему WA 1?
Posted by Mahilewets 22 Jul 2017 15:06
http://acm.timus.ru/status.aspx?space=1&num=1108&author=201928
Думаю в ваших решениях overflow происходит.
Re: Почему WA 1?
Posted by Mahilewets 22 Jul 2017 15:07
WA#1 у меня потому,  что  я проверял,  действительно ли первый тест -- это N=2
Re: Почему WA 1?
Posted by MassterMax`~ 22 Jan 2018 21:49
Я думаю, что здесь всего 1 тест сразу для случая, когда N=18. Лично я начал считать максимальные значения на калькуляторе и пришёл к одной закономерности.
I think that there is only one test right here for the case when N = 18. Personally, I started to count the maximum values ​​on the calculator and came to regularity.