Cod sursa(job #1005315)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 4 octombrie 2013 19:10:43
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

using namespace std;

long long int v[500005];
int pref[500005];

int main()
{
    ifstream cin("reguli.in");
    ofstream cout("reguli.out");

    int n=0,k=0,i;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>v[i];
    for(i=n-1;i>0;i--)
        v[i]=v[i]-v[i-1];
    n--;
    //for(i=1;i<=n;i++)
    //    cout<<v[i]<<' ';
    //cout<<endl;
    pref[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0 && v[i]!=v[k+1])
            k=pref[k];
        if(v[i]==v[k+1])
            k++;
        pref[i]=k;
    }
    n-=pref[n];

    cout<<n<<'\n';
    for(i=1;i<=n;i++)
        cout<<v[i]<<'\n';
    cin.close();
    cout.close();
    return 0;
}