Cod sursa(job #18291)

Utilizator mastermageSchneider Stefan mastermage Data 18 februarie 2007 11:17:05
Problema Reguli Scor 90
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.58 kb
#include <stdio.h>
#include <set>
#include <map>

using namespace std;

#define maxN 500100

int n;
long long vec[maxN];
int pos[maxN],p,k;

void inputFunc(){
	FILE*fi=fopen("reguli.in","r");
	fscanf(fi,"%ld",&n);
	for(int i=0;i<n;i++){
		fscanf(fi,"%lld",vec+i);
	}
	n--;
	for(int i=0;i<n;i++){
		vec[i]=vec[i+1]-vec[i];
	}
	
	fclose(fi);
}

void outputFunc(){
	FILE*fi=fopen("reguli.out","w");
	fprintf(fi,"%d\n",k);
	for(int i=0;i<k;i++){
		fprintf(fi,"%lld\n",vec[i]);
	}
	fclose(fi);
}

int main(){
	inputFunc();
	map<long long,int> mp,mpp;
	for(int i=0;i<n;i++){
		mp[vec[i]]++;
		if(mpp.find(vec[i])==mpp.end())mpp[vec[i]]=i;
	}
	map<long long,int>::iterator it,itp;
	
	int min=mp.begin()->second,pp=mpp.begin()->second;long long who=mp.begin()->first;
	for(it=mp.begin(),itp=mpp.begin(); it!=mp.end(); it++, itp++){
		if(min>it->second)min=it->second, who=it->first, pp=itp->second;else
		if(min==it->second && pp>itp->second)min=it->second, who=it->first, pp=itp->second;
	}
	
	for(int i=0;i<n;i++)if(vec[i]==who)pos[p++]=i;
	p--;for(int i=0;i<p;i++)pos[i]=pos[i+1]-pos[i];
	
	if(!p){
		int s=pos[0]+1;
		if(s<n/2)s=n/2-1;
		for(;s<n;s++){
			int flag=0;
			for(int j=s,l=0;j<n;j++,l++){
				if(vec[j]!=vec[l]){flag=1;break;}
			}
			if(!flag)break;
		}
		
		k=s;		
	}else{
		int s=0,flag;
		for(int i=0;i<p;i++){
			s+=pos[i];
			flag=0;
			for(int j=0;j<s;j++){
				for(int l=j;l<n;l+=s){
					if(vec[j]!=vec[l]){flag=1;break;}
				}
			}
			if(!flag)break;
		}
		if(!flag)k=s;else k=n;
	}
	
	outputFunc();
	return 0;
}