Pagini recente » Cod sursa (job #377947) | Cod sursa (job #2482206)
#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;
}