Cod sursa(job #2560827)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 28 februarie 2020 12:04:40
Problema Reguli Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 500005;

int N;
long long a[NMAX];
long long v[NMAX];
int lps[NMAX];

void Read()
{
    fin >> N;
    for( int i = 1; i <= N; ++i )
      fin >> a[i];
}

void Lps()
{
    int lg = 1;

    for( int i = 2; i < N; ++i )
      if( v[i] == v[lg] ) lps[i] = ++lg - 1;
      else
        if( lg > 1 ) {
           lg = lps[lg - 1];
           --i;
        }
}

void Do()
{
    for( int i = 1; i < N; ++i )
      v[i] = a[i + 1] - a[i];

    Lps();

    /*for( int i = 1; i <= N; ++i )
      fout << a[i] << ' ';
    fout << '\n';
    for( int i = 1; i < N; ++i )
      fout << v[i] << ' ';
    fout << '\n';
    for( int i = 1; i < N; ++i )
      fout << lps[i] << ' ';
    fout << '\n'; */

    int lmin = 0;
    for( int i = 1; i < N; ++i )
      if( lps[i] * 2 >= i ) {
        int aux = lps[i] * 2 - i;

        if( lps[i] - aux == 0 || aux % ( lps[i] - aux ) == 0 ) { lmin = lps[i]; break; }
      }

    fout << lmin << '\n';
    for( int i = 1; i <= lmin; ++i )
      fout << v[i] << '\n';
}

int main()
{
    Read();
    Do();

    return 0;
}