Cod sursa(job #50531)

Utilizator vlad_popaVlad Popa vlad_popa Data 7 aprilie 2007 20:58:51
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <string>

#define FIN "reguli.in"
#define FOUT "reguli.out"
#define NMAX 500001

long long a[NMAX];
int pi[NMAX], N;
char s[32], ok[NMAX];

void read ()
{
    long long l, ct, x;
    scanf ("%d\n", &N);

    for (int i = 1; i <= N; ++ i)
    {
        gets (s);
        
        l = strlen (s);
        ct = 1;
        x = 0;

        for (int j = l - 1; j >= 0; -- j)
        {
            x += (s[j] - '0') * ct;
            ct *= 10;
        }

        a[i] = x;
        a[i-1] = a[i] - a[i-1];
    }

    N--;
}

void prefix ()
{
    int k = 0;
    
    for (int i = 2; i <= N; ++ i)
    {
        while (k > 0 && a[k + 1] != a[i])
            k = pi[k];

        if (a[k + 1] == a[i])
            ++ k;
        pi[i] = k;
    }
}

void okeul ()
{
    ok[0] = 1;

    for (int i = 1; i <= N; ++ i)
        if (a[i] == a[N - i + 1])
            ok[i] = 1;
        else
            break;
}

void solve ()
{
    prefix ();
    okeul ();

    int r, c;
    for (int L = 1; L <= N; ++ L)
    {
        r = N % L;
        c = N / L;
        if (pi[N - r] > 0 && (N - r) % (N - r - pi[N - r]) == 0)
            if (ok[r] == 1 && (N - r) / (N - r - pi[N - r]) == c)
            {
                printf ("%d\n", L);
                for (int i = 1; i <= L; ++ i)
                    printf ("%d\n", a[i]);
                break;
            }
    }
}

int
 main ()
{
    freopen (FIN, "rt", stdin);
    freopen (FOUT, "wt", stdout);

    read ();
    solve ();

    return 0;
}