Cod sursa(job #1403702)

Utilizator ThomasFMI Suditu Thomas Thomas Data 27 martie 2015 15:27:13
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
using namespace std;

#define NMax 500005

ifstream f("reguli.in");
ofstream g("reguli.out");

int n;
int v[NMax];
int pi[NMax];

void pref()
{
    int i,q=0;
    pi[1] = 0;
    for(i=2;i<n;++i)
    {
        while(q && v[q+1]!=v[i]) q=pi[q];
        if(v[q+1]==v[i]) q++;
        pi[i] = q;
    }
}

int main()
{
    int i,a,b;
    f>>n>>a;
    for(i=1;i<n;++i)
    {
        f>>b;
        v[i] = b-a;
        a = b;
    }

    pref();

    int mx = 0;

    for(i=n-1;i>=1;--i) if(pi[i] && i%(i-pi[i])==0)
    {
        mx = i-pi[i];
        break;
    }

    g<<mx<<"\n";
    for(i=1;i<=mx;++i) g<<v[i]<<"\n";

    f.close();
    g.close();
    return 0;
}