Cod sursa(job #2482206)

Utilizator hunting_dogIrimia Alex hunting_dog Data 27 octombrie 2019 21:19:53
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

vector <unsigned long> make_lps(vector <long> &s)
{
    vector <unsigned long> lps;
    lps.push_back(0);
    int i=0,j=1,n=s.size();
    while(j<n)
    {
        if(s[i]==s[j])
            ++i,lps.push_back(i),++j;
        else
            if(i!=0)
                i=lps[i-1];
            else
                lps.push_back(0),++j;
    }
    return lps;
}

int main()
{
    int n;
    f>>n;
    vector <unsigned long> v;
    while(n--)
    {
        unsigned long x;
        f>>x;
        v.push_back(x);
    }
    int m=v.size();
    vector <long> t;
    for(int i=1;i<m;++i)
        t.push_back(v[i]-v[i-1]);
    v=make_lps(t);
    --m;
    while(m>0 && (!v[m-1] || m%(m-v[m-1])))
        --m;
    if(!m)
    {
        g<<t.size()<<'\n';
        for(auto x:t)
            g<<x<<'\n';
        return 0;
    }
    m-=v[m-1];
    g<<m<<'\n';
    for(int i=0;i<m;++i)
        g<<t[i]<<'\n';

    return 0;
}