Cod sursa(job #1479599)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 31 august 2015 17:47:29
Problema Reguli Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#define MAX 500005
 
int n, i, p[MAX];
long long x[MAX];

void prefix();
 
int main(){
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%lld", &x[i]);
    for(i = n - 1; i > 0; i--)
        x[i] -= x[i - 1];
    prefix();
    n--;
    printf("%d\n", n - p[n]);
    for(i = 1; i <= n - p[n]; i++)
        printf("%lld\n", x[i]);
    return 0;
}
 
void prefix(){
    int i, k = 0;
    for(i = 2; i < n; i++){
        while(k > 0 && x[k + 1] != x[i])
            k = p[k];
        if(x[k + 1] == x[i])
            k++;
        p[i] = k;
    }
}