Mai intai trebuie sa te autentifici.
Cod sursa(job #578633)
Utilizator | Data | 11 aprilie 2011 13:58:23 | |
---|---|---|---|
Problema | Reguli | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.75 kb |
#include<fstream>
#define LL long long
using namespace std;
const int MaxN = 500005;
const char InFile[] = "reguli.in";
const char OutFile[] = "reguli.out";
LL s[MaxN];
int N,sol,urm[MaxN];
int KMP()
{
int q,k,T;
T = N-1;
k = 0;
urm[0] = urm[1] = 0;
for( q = 2 ; q < N ; q++ )
{
while( k > 0 && s[q] != s[k+1] )
k = urm[k];
if( s[q] == s[k+1] )
k++;
if( k && !(q%(q-k)) )
T = q-k;
}
return T;
}
int main()
{
ifstream f ( InFile );
ofstream g ( OutFile );
LL x,y;
int i;
f >> N >> x;
for( i = 1 ; i < N ; i++ )
{
f >> y;
s[i] = y-x;
x = y;
}
int T;
T = KMP();
g << T << '\n';
for( i = 1 ; i <= T ; i++ )
g << s[i] << '\n';
f.close();
g.close();
return 0;
}