Cod sursa(job #1561789)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 4 ianuarie 2016 15:44:38
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAX_N = 500000;

int n;
long long V[1 + MAX_N];
long long D[1 + MAX_N];
int PI[1 + MAX_N];
bool equalPrefSuf[1 + MAX_N];

bool testLength(int L) {
    int k = n / L, r = n % L;

    return(PI[n - r] > 0 &&
           (n - r) % (n - r - PI[n - r]) == 0 &&
           (n - r) / (n - r - PI[n - r]) == k &&
           equalPrefSuf[r]);
}

int main() {
    int i, l, q;

    in >> n >> V[0];
    n--;
    for(i = 1; i <= n; i++) {
        in >> V[i];
        D[i] = V[i] - V[i - 1];
    }

    for(i = 2, q = 0; i <= n; i++) {
        while(q > 0 && D[q + 1] != D[i]) q = PI[q];
        if(D[q + 1] == D[i]) q++;
        PI[i] = q;
    }

    for(q = PI[n]; q > 0; q = PI[q]) {
        equalPrefSuf[q] = true;
    }
    for(l = 1; l <= n && testLength(l) == false; l++);

    if(l > n) l--;
    out << l << '\n';
    for(i = 1; i <= l; i++) {
        out << V[i] - V[i - 1] << '\n';
    }

    return 0;
}