Cod sursa(job #1838597)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 1 ianuarie 2017 14:14:13
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#define MAXN 500000
using namespace std;

long long d[MAXN + 1];
int pi[MAXN + 1];

void calc_pi(int n) {
    int k = 0;

    for (int i = 2 ; i <= n ; ++i) {
        while (k && d[k + 1] != d[i])
            k = pi[k];

        if (d[k + 1] == d[i])
            ++k;

        pi[i] = k;
    }
}

inline bool perioada(int l, int n) {
    int r = n % l;

    if (pi[n] < r)
        return false;

    if (pi[n - r] == 0)
        return false;

    int diff = n - r - pi[n - r];
    if ((n - r) % diff != 0)
        return false;
    if ((n - r) / diff != (n / l))
        return false;

    return true;
}

int main () {
    ifstream cin("reguli.in");
    ofstream cout("reguli.out");

    int n;
    cin >> n;

    int prev, x;
    cin >> prev;
    for (int i = 1 ; i < n ; ++i) {
        cin >> x;
        d[i] = x - prev;
        prev = x;
    }

    calc_pi(n - 1);

    bool solved = false;
    for (int l = 1 ; l < n - 1 && !solved ; ++l) { //!!pt lungime chiar n
        if (perioada(l, n - 1)) {
            solved = true;
            cout << l << "\n";
            for (int i = 1 ; i <= l ; ++i)
                cout << d[i] << "\n";
        }
    }

    if (!solved) {
        cout << n - 1 << "\n";
        for (int i = 1 ; i < n ; ++i)
            cout << d[i] << "\n";
    }

    return 0;
}