Cod sursa(job #1328929)

Utilizator diana97Diana Ghinea diana97 Data 28 ianuarie 2015 21:32:50
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 500000 + 1;

int n;
long long v[NMAX];
int p[NMAX];

void citeste() {
    f >> n;
    long long x, y;
    f >> v[0];
    x = v[0];
    for (int i = 1; i < n; i++) {
        f >> y;
        v[i] = y - x;
        x = y;
    }
}

void rezolva() {
    p[0] = p[1] = 0;
    int k = 0;
    for (int i = 2; i < n; i++) {
        while (k != 0 && v[k + 1] != v[i]) k = p[k];
        if (v[k + 1] == v[i]) k++;
        p[i] = k;
    }
    g << p[n - 1] - 1 << '\n';
    for (int i = 1; i < p[n - 1]; i++) g << v[i] << '\n';
}

int main() {
    citeste();
    rezolva();
    return 0;
}