Cod sursa(job #1516990)

Utilizator DoraBenzoVelicu Teodora DoraBenzo Data 3 noiembrie 2015 19:30:15
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#define nmax 50001

using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");

int n, x[nmax], pref[nmax], a[nmax];

void pattern()
{
    int i, j;
    i=1;
    j=0;
    pref[0] = 0;
    while(i < n)
        if(x[i] == x[j])
        {
            pref[i] = j+1;
            i++;
            j++;
        }
        else
            if(j == 0)
                pref[i++]=0;
            else
                j=pref[j-1];
}

int cautare(int lp)
{
    for(int i=lp-1; i>=0; i--)
            if(((i+1) % ((i+1) - pref[i])) == 0 && pref[i])
                return (i+1) - pref[i];
    return 0;
}

int main()
{
    fin >> n;

    for(int i=1; i<=n; i++)
    fin >> a[i];
    for(int i=0; i<n-1; i++)
        x[i] = a[i+2] - a[i+1];
    pattern();
    int m = cautare(n);
    fout<<m<<"\n";
    for(int i=0; i<m; i++)
        fout<<x[i]<<"\n";
    return 0;
}