Cod sursa(job #1460008)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 11 iulie 2015 14:17:05
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 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;

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

    fout << Sol << "\n";

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

  return 0;
}