Cod sursa(job #1025515)

Utilizator ericptsStavarache Petru Eric ericpts Data 10 noiembrie 2013 10:17:20
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream in("reguli.in");
ofstream out("reguli.out");
const int MAX_N = 5 * int(1e5) + 100;

int n;
int v[MAX_N];
int diff[MAX_N];
int phi[MAX_N];

void KMP(int * arr, const int n){

    int now = 1;
    phi[1] = -1;

    for(int i = 2 ; i <= n ;) {

        if(arr[i] == arr[now]) {
            phi[i] = now;
            ++now;
            ++i;
        } else if(phi[now] != -1) {
            now = phi[now];
        } else {
            now = 1;
            phi[i] = now;
            ++i;
        }
    }
}

int main()
{
    in >> n;
    for(int i = 1 ; i <= n ; ++i)
        in >> v[i];

    --n;
    for(int i = 1 ; i <= n ; ++i)
        diff[i] = v[i + 1] - v[i];

    KMP(diff, n);
    if(phi[n] == 1 && diff[n] != diff[1])
        --phi[n];
    out << n - phi[n] << "\n";
    for(int i = 1 ; i <= n - phi[n] ; ++i)
        out << diff[i] << "\n";

    return 0;
}