Cod sursa(job #1460010)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 11 iulie 2015 14:24:16
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

const int Dim = 500001;

long long N,T[Dim],D[Dim],P[Dim],Sol,X;

int main()
{
    fin >> N;

    for (int i = 0;i <= N - 1;i++)
        fin >> T[i];

    for (int i = 1;i <= N - 1;i++)
        D[i] = T[i] - T[i - 1];

    for (int i = 2;i <= N - 1;i++)
    {
        while(X > 0 && D[i] != D[X + 1])
            X = P[X];

        if (D[X + 1] == D[i])
            X++;

        P[i] = X;

    }

    N--;

    for (int i = 1;i <= N;i++)
    {
        int R = N % i,C = N / i,L = N - R;
        bool ok = true;

        for (int i = 1;i <= R;i++)
            if (D[i] != D[N - i + 1])
            {
                ok = false;
                break;
            }

        if (P[L] && !(L % (L - P[L])) && (L / (L - P[L]) == C) && ok)
        {
            Sol = i;
            break;
        }
    }
    if (!Sol) Sol = N;

    fout << Sol << "\n";

    for (int i = 1;i <= Sol;i++)
        fout << D[i] << "\n";

  return 0;
}