Cod sursa(job #2351006)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 21 februarie 2019 21:22:17
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <cstdio>
using namespace std;

int n, a[500005], prefix[500005], x, y, l;

void pref()
{
    int k = 0;
    for(int i = 2; i<=n; i++)
    {
        while(a[i] != a[k+1] && k>0)
        {
            k = prefix[k];
        }
        if(a[i] == a[k+1])
            k++;
        prefix[i] = k;
    }
}

void rez()
{
    scanf("%d %d", &n, &x);
    for(int i = 1; i<=n; i++)
    {
        scanf("%d", &y);
        a[i] = y-x;
        x = y;
    }
    pref();
    for(int i = n-1; i>0; i--)
    {
        if(prefix[i]%(i-prefix[i]) == 0)
        {
            while(prefix[i] != 0 && prefix[prefix[i]]%(prefix[i]-prefix[prefix[i]]) == 0)
                i = prefix[i];
            l = i;
            break;
        }
    }
    /*for(int i = 1; i<=n; i++)
    {
        printf("%d ", prefix[i]);
    }
    printf("\n");
    for(int i = 1; i<=n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");*/
    printf("%d\n", l);
    for(int i = 1; i<=l; i++)
    {
        printf("%d\n", a[i]);
    }
}

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    rez();
    return 0;
}