Cod sursa(job #2482188)

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

using namespace std;

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

vector <int> make_lps(vector <int> &s)
{
    vector <int> 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 <int> v;
    while(n--)
    {
        int x;
        f>>x;
        v.push_back(x);
    }
    int m=v.size();
    for(int i=1;i<m;++i)
        v[i-1]=v[i]-v[i-1];
    v.pop_back();
    vector <int> t=v;
    v=make_lps(v);
    --m;
    while(m>0 && (!v[m-1] || m%(m-v[m-1])))
        --m;
    m-=v[m-1];
    g<<m<<'\n';
    for(int i=0;i<m;++i)
        g<<t[i]<<'\n';

    return 0;
}