Cod sursa(job #912453)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 12 martie 2013 14:05:50
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
using namespace std;

#define Nmax 500005

long long int n, pi[Nmax], sir[Nmax], maxx;

void prefix(){
    int k = 0;
    for(int i = 2; i < n; ++i){
        while(sir[i] != sir[k+1] && k > 0) k = pi[k];
        if(sir[i] == sir[k+1]) ++k;
        pi[i] = k;
    }
}

void read(){
    scanf("%i", &n);
    int x1, x2;
    scanf("%i", &x1);
    for(int i = 1; i < n; ++i){
        scanf("%i", &x2);
        sir[i] = x2 - x1;
        x1 = x2;
    }
    fclose(stdin);
}

void solve(){
    prefix();

    bool found = false;
    for(int i = n-1; i > 0 && !found; --i){
        if(pi[i] && i%(i - pi[i]) == 0){
            maxx = i - pi[i];
            found = true;
        }
    }
}

void write(){
    printf("%i\n", maxx);
    for(int i = 1; i <= maxx; ++i) printf("%i\n", sir[i]);
    fclose(stdout);
}

int main(){
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);

    read();
    solve();
    write();

    return 0;
}