Cod sursa(job #2457952)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 19 septembrie 2019 10:23:52
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb

#include <iostream>	
#include <fstream>
#include <cstring>
using namespace std;
	
ifstream fin("reguli.in");
	
ofstream fout("reguli.out");
	
const int NMAX = 500000 + 5;
	
const int INF = 0x3f3f3f3f;
	
int n, len, period;
	
long long int minim = INF;
	
long long int v[NMAX], phi[NMAX];
		
int main()
	
{
	
   
    long long int x1, x2;
	
    fin >> n >> x1;
	
    for (int i = 2; i <= n; ++i)
	
    {
        fin >> x2;
        v[++len] = x2 - x1;
        x1 = x2;
    }
	
    for (int i = 2; i <= len; ++i)
	
    {
	
        int last = phi[i - 1];
	
        while (last > 0 && v[i] != v[last + 1]) last = phi[last];
	
        if (v[i] == v[last + 1]) phi[i] = last + 1;
	
    }
    for (int i = 1; i <= len; ++i)
        if (i % (i - phi[i]) == 0 && phi[i] && phi[len] == len - (i - phi[i])) 
            minim = min(minim, i - phi[i]);
     if (minim != INF)
	
    {
	
        fout << minim << '\n';
	
        for (int i = 1; i <= minim; ++i)
	
            fout << v[i] << '\n';
	
    }
	
    else
	
    {
	
        fout << len << '\n';
        for (int i = 1; i <= len; ++i)
	
            fout << v[i] << '\n';
	
    }
	
	
 
	
    return 0;
	
}