Cod sursa(job #2117205)

Utilizator 24601Dan Ban 24601 Data 28 ianuarie 2018 17:50:28
Problema Reguli Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>

#define SIZE 500001

static long long x[SIZE];
static size_t pi[SIZE];

int main(void)
{
    size_t n, i, q;
    long long prev, c;
    char ok;

    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);

    scanf("%lu %lld", &n, &prev);

    for (i = 1; i < n; i++) {
        scanf("%lld", &c);
        x[i] = c - prev;
        prev = c;
    }

    pi[1] = 0;
    q = 0;

    for (i = 2; i < n; i++) {
        while (q > 0 && x[q + 1] != x[i]) {
            q = pi[q];
        }

        if (x[q + 1] == x[i]) {
            q++;
        }

        pi[i] = q;
    }

    for (i = n - 1; i > 0; i--) {
        if (i % (i - pi[i]) == 0) {
            ok = 1;
            for (q = 1; ok && q <= n - 1 - i; q++) {
                if (x[i + q] != x[q]) {
                    ok = 0;
                }
            }

            if (ok) {
                printf("%lu\n", i - pi[i]);
                for (q = 1; q <= i - pi[i]; q++) {
                    printf("%lld\n", x[q]);
                }
            } else {
                printf("%lu\n", n - 1);
                for (q = 1; q < n; q++) {
                    printf("%lld\n", x[q]);
                }
            }

            break;
        }
    }

    return 0;
}