Cod sursa(job #1496046)

Utilizator cristina_borzaCristina Borza cristina_borza Data 4 octombrie 2015 10:36:51
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>

#define NMAX  500005

using namespace std;

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

int n , a , b , v[NMAX] , pi[NMAX] , sol;

int main()
{
    f >> n >> a;
    for(int i = 1 ; i < n ; ++i) {
        f >> b;
        v[i] = b - a;
        a = b;
    }

    int k = 0;
    pi[1] = 0;
    for(int i = 2 ; i < n ; ++i) {
        while(k > 0 && v[k + 1] != v[i]){
            k = pi[k];
        }
        if(v[k + 1] == v[i]){
            ++k;
        }
        pi[i] = k;
    }
    sol = n - 1 - pi[n - 1];
    g << sol << '\n';
    for(int i = 1 ; i <= sol ; ++i){
        g << v[i] << '\n';
    }
    return 0;
}