Cod sursa(job #343702)

Utilizator marinaMarina Horlescu marina Data 26 august 2009 21:47:41
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#define INPUT "curcubeu.in"
#define OUTPUT "curcubeu.out"

int n;
int tata(int i, int *next)
{
	if(!next[i]) return i; 
	return next[i] = tata(next[i], next);
}

int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	int a, b, c;
	scanf("%d %d %d %d", &n, &a, &b, &c);
	
	int *next = new int[n+1];
	int *color = new int[n+1];
	int i;
	for(i = 0; i < n; ++i) 
		color[i] = 0,
		next[i] = 0;
	
	int *queuea = new int[n-1];
	int *queueb = new int[n-1];
	int *queuec = new int[n-1];
	

	queuea[0] = a; queueb[0] = b; queuec[0] = c;
	
	for(i = 1; i < n-1; ++i)
	{
		queuea[i] = (queuea[i-1]*(i+1)) % n;
		queueb[i] = (queueb[i-1]*(i+1)) % n;
		queuec[i] = (queuec[i-1]*(i+1)) % n;
	}

	for(i = n-2; i >= 0; --i)
	{	
		int a = queuea[i], b = queueb[i], c = queuec[i];
		--a; --b;
		if(a > b) a+=b, b=a-b, a-=b; //interschimb
		int ii;
		for(ii = a; ii < n && ii <= b;)
			if(!color[ii]) 
			{
				color[ii] = c;
				next[ii] = tata(b+1, next);
				++ii;
			}
			else ii = next[ii];
	}
	for(i = 0; i < n-1; ++i)
		printf("%d\n", color[i]);
	return 0;
}