Cod sursa(job #18267)

Utilizator scapryConstantin Berzan scapry Data 18 februarie 2007 11:07:07
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.1 kb
#include <stdio.h>
#include <string.h>

enum { maxn = 500001 };

int n;
long long s[maxn];
long long p[maxn];

int main()
{
	int i, j, ans = -1;
	long long x;
	FILE *f = fopen("reguli.in", "r");
	if(!f) return 1;
	
	fscanf(f, "%d", &n);
	for(i = 0; i < n; i++) fscanf(f, "%lld", &s[i]);
	
	fclose(f);
	f = fopen("reguli.out", "w");
	if(!f) return 1;
	
	for(i = 1; i < n; i++) p[i] = s[i] - s[i - 1];
	
	x = p[1];
	for(i = 2; i < n; i++)
	{
		x ^= p[i];
		
		if(x) continue;
		if( memcmp(&p[1], &p[i / 2 + 1], i / 2 * sizeof(p[0])) ) continue;
		
		for(j = i + 1; j + i < n; j += i)
			if( memcmp(&p[1], &p[j], i * sizeof(p[0])) )
				break;
		
		if(j + i < n) continue; //broke
		if( memcmp(&p[1], &p[j], (n - j) * sizeof(p[0])) ) continue; //bad suffix
		
		ans = i / 2 + 1;
		break; //solution!
	}
	
	if(ans == -1)
	{
		//is it "repeating" only once + suffix?
		for(i = n / 2 + 1; i < n; i++)
			if( memcmp(&p[1], &p[i], (n - i) * sizeof(p[0])) == 0)
				break;
		
		if(i != n) ans = i;
		else ans = n;
	}
	
	fprintf(f, "%d\n", ans - 1);
	for(i = 1; i < ans; i++)
		fprintf(f, "%lld\n", p[i]);
	
	fclose(f);
	return 0;
}