Cod sursa(job #1430327)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 8 mai 2015 10:41:25
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>

using namespace std;

const int nmax = 500000;

int n;
long long a[nmax+5];
int pi[nmax+5];
bool ok[nmax+5];

void prefix()
{
    pi[1] = 0;
    int q = 0;
    for(int i=2; i<=n; i++)
    {
        while(q && a[q+1] != a[i])
            q=pi[q];
        if(a[q+1] == a[i])
            q++;
        pi[i] = q;
    }
}

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    scanf("%d", &n);
    long long x, y;
    scanf("%lld", &x);
    for(int i=1; i<n; i++)
	{
        scanf("%lld", &y);
        a[i] = y-x;
        x = y;
	}
	n--;
	prefix();
	int k = n;
	ok[n] = true;
	while(pi[k])
	{
		k = pi[k];
		ok[k] = true;
	}
	for(int l=1; l<=n; l++)
	{
		int r = n%l;
		int c = n/l;
		if(ok[r] && pi[n-r] && (n-r)%(n-r-pi[n-r]) == 0 && (n-r)/(n-r-pi[n-r]) == c)
		{
			printf("%d\n", l);
			for(int i=1; i<=l; i++)
				printf("%lld\n", a[i]);
			return 0;
		}
	}
    return 0;
}