Cod sursa(job #2557997)

Utilizator RedXtreme45Catalin RedXtreme45 Data 26 februarie 2020 10:39:20
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
long long int n,a,b,stare[500001];
vector <long long int> v;
int main()
{
    int i;
    fin>>n;
    fin>>a;
    for (i=1;i<n;i++)
    {
        fin>>b;
        v.push_back(b-a);
        a=b;
    }
    int x=v.size(),st=0;
    for (i=2;i<=x;i++)
    {
        while (st>0 && v[st]!=v[i-1])
            st=stare[st];
        if (v[st]==v[i-1])
            st++;
        stare[i]=st;
    }
    int lung;
    for (i=1;i<=x;i++)
    {
        if (stare[i]>=(i+1)/2 && stare[i]%(i-stare[i])==0)
        {
            lung=i-stare[i];
            fout<<i-stare[i];
            break;
        }
    }
    fout<<"\n";
    for (i=0;i<lung;i++)
        fout<<v[i]<<"\n";
    return 0;
}