Cod sursa(job #2460531)

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

using namespace std;

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

int n, d[NMAX+10], v[NMAX+10], phi[NMAX+10];

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