Cod sursa(job #2460542)

Utilizator FrostfireMagirescu Tudor Frostfire Data 23 septembrie 2019 21:27:12
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <iostream>
#define NMAX 500000

using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");

long long n, d[NMAX+100], v[NMAX+100], phi[NMAX+100];

int main()
{
    f >> n >> v[0];
    for(int i=1; i<n; i++)
        {   f >> v[i];
            d[i-1] = v[i] - v[i-1];
        }
    long long i = 1, j = 0;
    while(i < n-1)
        {   if(d[i] == d[j])
                {   j++;
                    phi[i] = j;
                    i++;
                }
            else
                {   if(j) j = phi[j-1];
                    else i++;
                }
        }
    long long l = n-1-phi[n-2];
    g << l << '\n';
    for(int i=0; i<l; i++) g << d[i] << '\n';
    return 0;
}