Cod sursa(job #18909)

Utilizator blasterzMircea Dima blasterz Data 18 februarie 2007 14:52:13
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<cstdio>
#include <hash_map.h>
#include <string>
#include <cstdlib>
#include <map>
#define maxn 500001
using namespace std;

char aux[30*maxn];
long long x[maxn];
long long dif[maxn];
int n;

void citire()
{
	freopen("reguli.in", "r", stdin);
	scanf("%d\n", &n);
	fread(aux, sizeof(char), 500001*30, stdin);
	char *p;
	p=strtok(aux, " \n");
	x[1]=atoll(p);	
	int i;
	for(i=2;i<=n;i++)
	{
		p=strtok(0, " \n");
		x[i]=atoll(p);
	}
	

	for(i=2;i<=n;i++) dif[i]=x[i]-x[i-1];
	
}

void calcul()
{
	int i, j;
      hash_map<long long,bool,hash<long long> > Q;
	
	Q[dif[2]]=1;
	
	for(i=3;i<=n;i++)
	{
	  // printf("%lld %d\n", dif[i], Q[dif[i]]);
	  if(Q[dif[i]])
		{
			int ok=1;
			int k=Q.size(), p;
			for(j=2;j<=n;j++) 
			  {
			    if((j-1)%k==0) p=k+1;
			    else p=((j-1)%k)+1;
			    //printf("(%lld %lld) %d %d\n", x[j], x[j-1]+dif[p],j,p);
				if(x[j]!=x[j-1]+dif[p]) {ok=0;break;}
			}
			if(ok)
			{
			  int nr=0;
			  for(j=2;j<i;j++) nr++;
			  printf("%d\n", nr);
			  for(j=2;j<i;j++) printf("%lld\n",dif[j]);
			return;
			}
		}
	  Q[dif[i]]=1;
	}
	
}


int main()
{
	citire();
	freopen("reguli.out", "w", stdout);
	calcul();
	return 0;
}