Cod sursa(job #2189703)

Utilizator cc4infinityCojocaru Catalin cc4infinity Data 28 martie 2018 20:56:52
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <fstream>

using namespace std;
int n,i,j,s,t[500004];
long long z,x,y,nr[500004];
int main()
{
    ifstream fin("reguli.in");
    ofstream fout("reguli.out");
    fin>>n;
    fin>>x;
    n--;
    for (i=1;i<=n;i++)
    {
        fin>>y;
        nr[i]=y-x;
        x=y;
    }
    int k=0;
    for (i=2;i<=n;i++)
    {
        while (k>0 && nr[k+1]!=nr[i]) k=t[k];
        if (nr[k+1]==nr[i]) k++;
        t[i]=k;
    }
    //if (k>=n/2+n%2) fout<<n-k; else fout<<n;
    fout<<n-k;
    return 0;
}