Cod sursa(job #856986)

Utilizator SteveStefan Eniceicu Steve Data 17 ianuarie 2013 09:34:38
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <stack>
#include <bitset>
#include <list>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp(a,b) make_pair (a, b)
#define ll long long
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)

using namespace std;

int N;
long long v[500011];
int Pi[500011];

void Citire ()
{
    ifstream fin ("reguli.in");
    fin >> N;
    fin >> v[0];
    for (int i = 1; i < N; i++)
        fin >> v[i];
    for (int i = N - 1; i >= 1; i--)
        v[i] -= v[i - 1];
    N--;
    fin.close ();
}

void Precalculare ()
{
    for (int i = 2, p = 0; i <= N; i++)
    {
        while (p && v[i] != v[p + 1]) p = Pi[p];
        if (v[i] == v[p + 1]) p++;
        Pi[i] = p;
    }
}

int Business ()
{
    int a;
    for (int K = 1; K <= N; K++)
    {
        a = N - (N % K);
        if (Pi[a] && !(a % (a - Pi[a])))
        {
            if (Pi[N] == Pi[N - K] + K && v[N] == v[N - K]) return K;
        }
    }
    return N;
}

void Scriere ()
{
    ofstream fout ("reguli.out");
    int a = Business ();
    fout << a << "\n";
    for (int i = 1; i <= a; i++)
        fout << v[i] << "\n";
    fout.close ();
}

int main ()
{
    Citire ();
    Precalculare ();
    Scriere ();
    return 0;
}