Cod sursa(job #2189703)
| Utilizator | 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;
}
