Cod sursa(job #572061)

Utilizator Sm3USmeu Rares Sm3U Data 4 aprilie 2011 23:33:27
Problema Reguli Scor 70
Compilator cpp Status done
Runda brasov_11_jr Marime 0.99 kb
#include <stdio.h>

using namespace std;

int a[500000];
int b[500000];
int n;

void KMP()
{
    int i=0;
    int j=-1;
    b[0]=-1;
    while(i<n)
    {
        while(j>=0 && a[i]!=a[j])
            j=b[j];
        i++;
        j++;
        b[i]=j;
    }
}

void citire()
{
    scanf("%d",&n);
    n--;
    int c;
    int d;
    scanf("%d",&c);
    scanf("%d",&d);
    a[0]=d-c;
    for(int i=1;i<n;i++)
    {
        c=d;
        scanf("%d",&d);
        a[i]=d-c;
    }

}


int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    citire();
    KMP();
    int i=1;
    while(b[i]==0)
        i++;
    i--;
    for(;i<n;i++)
    {
        int r=n%i;
        int c=n/i;
        if(n-r>0 && b[n-r]>0 && (n-r)%(n-r-b[n-r])==0 && (n-r)/(n-r-b[n-r])==c)
        {
            printf("%d\n",i);
            for(int j=0;j<i;j++)
                printf("%d\n",a[j]);
            return 0;
        }
    }
    return 0;
}