Cod sursa(job #852841)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 11 ianuarie 2013 20:17:55
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <cstring>
using namespace std;
int x, xlast, i, n, k, pi[500010];
int a[500010];
void prefix()
{
    k = 0;
    for(i = 2; i <= n; i++)
    {
        while(k and a[i] != a[k+1]) k = pi[k];
        if(a[i] == a[k+1]) k++;
        pi[i] = k;
    }
}
int main()
{
    ifstream fi("reguli.in");
    ofstream fo("reguli.out");
    fi >> n;
    for(i = 1; i <= n; i++)
    {
        xlast = x;
        fi >> x;
        if(i > 1) a[i-1] = x - xlast;
    }
    n--;
    prefix();
    k = n - pi[n];
    fo << k << "\n";
    for(i = 1; i <= k; i++) fo << a[i] << "\n";
    return 0;
}