Cod sursa(job #1563884)

Utilizator serbanSlincu Serban serban Data 7 ianuarie 2016 00:03:06
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<long long> r;
long long a[500005];
long long b[500005];
int pi[500005];

int main()
{
    FILE *f = fopen("reguli.in", "r"),
         *g = fopen("reguli.out", "w");
    int n;
    fscanf(f, "%d", &n);
    for(int i = 1; i <= n; i ++) fscanf(f, "%lld", &a[i]);
    for(int i = 1; i < n; i ++) b[i] = a[i + 1] - a[i];
    int k = 0;
    for(int i = 2; i < n; i ++) {
        while(k && b[i] != b[k + 1]) k = pi[k];
        if(b[i] == b[k + 1]) k ++;
        pi[i] = k;
    }
    int ret = n - 1 - pi[n - 1];
    fprintf(g, "%d\n", ret);
    for(int i = 1; i <= ret; i ++) fprintf(g, "%lld\n", b[i]);
    return 0;
}