Cod sursa(job #1213466)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 28 iulie 2014 11:26:18
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <iostream>
typedef struct nod{long long val;nod *urm;}Stack;
Stack *st;
using namespace std;
long long phi[500005];
long long x,y,v[500005];
void prefix(long long *v,int size)
{
	int i,k;
	k=0;
	phi[1]=0;
	for(i=2;i<=size;++i)
	{
		while(k>0 && v[k+1]!=v[i])
			k=phi[k];
		if(v[k+1]==v[i]) ++k;
		phi[i]=k;
	}
}

void addToStack(Stack *&s,long long value)
{
	Stack* e=new nod;
	e->val=value;
	e->urm=s;
	s=e;
}
int main()
{
	ifstream f("reguli.in");
	ofstream g("reguli.out");
	int n,i,total;
	f>>n;
	f>>x;
	for(i=2;i<=n;++i)
	{
		f>>y;
		v[i-1]=y-x;
		x=y;
	}
	--n;
	prefix(v,n);
	i=n;
	total=n-phi[n];
	for(i=total;i>=1;--i) addToStack(st,v[i]);
	g<<total<<"\n";
	for(Stack *p=st;p;p=p->urm) g<<p->val<<"\n";
	f.close();
	g.close();
	return 0;
}