Cod sursa(job #881428)

Utilizator vendettaSalajan Razvan vendetta Data 17 februarie 2013 22:46:31
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");

#define nmax 500005
#define ll long long

int n;
ll a[nmax];
int pi[nmax];

void citeste(){
    f >> n;
    ll x0, x; f >> x0;
    for(int i=1; i<n; ++i){
        f >> x;
        a[i] = x - x0;
        x0 = x;
    }
}

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

inline bool check(int i, int j){
    for(int k=i; k<n; ++k){
        int poz = k % j; if (poz == 0) poz = j;
        if (a[k] != a[poz]) return 0;
    }
    return 1;
}

void rezolva(){
    // acum am vectorul cu ratii trebuie sa determin cel mai mic ciclu
    // bag un brut
    int Rez = 0;
    for(int i=1; i<n; ++i){
        if ( check( 1, i ) == 1 ){
            Rez = i; break;
        }
    }
    g << Rez << "\n";
    //cout << Rez << "\n";
    for(int i=1; i<=Rez; ++i){
        //cout << a[i] << "\n";
        g << a[i] << "\n";
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}