Cod sursa(job #239797)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 5 ianuarie 2009 21:34:57
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
long long a[500003];
long long b[500003];
char v[500003];
int P[500003];
int n;
int contor;

int PI()
{
    int k = 0;
    P[1] = 0;
    for(int i = 2; i <= n; i++)
      {
          while (b[i] != b[k+1] && k != 0)
           k = P[k];
          if (b[i] == b[k+1]) k++;
          P[i] = k;
      }
}

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

    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
     scanf("%lld",&a[i]);
    for(int i = 2; i <= n; i++)
     b[i-1] = a[i] - a[i - 1];
    PI();
    int k = P[n-1];
    while (k)
     {
         v[k] = 1;
         k = P[k];
     }
    n--;
     for(int PD = 1; PD <= n; PD++)
       {
           int c = (n) / PD;
           int r = (n) % PD;
           int ok = 1;
           if (P[n-r] == 0) ok = 0;
           if (((n-r) % (n - r - P[n-r])) != 0) ok = 0;
           if (((n-r) / (n - r - P[n-r])) != c) ok = 0;
           if (!v[r]) ok = 0;
           if (ok)
             {
                 printf("%d\n",PD);
                 for(int i = 1; i <= PD; i++)
                  printf("%lld\n",b[i]);
                 PD = n;
             }


       }
    return 0;
}