Cod sursa(job #109573)

Utilizator alextheroTandrau Alexandru alexthero Data 25 noiembrie 2007 11:56:45
Problema NKPerm Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 1, Clasele 11-12 Marime 1.58 kb
#include <stdio.h>

#define tmax 1005
#define nmax 21
#define kmax 6

int n, k, t, ct = 0, aType, bType, ram;
int a[tmax][nmax * kmax], b[tmax], v[nmax];
int nextRez[tmax][2];
int ax[nmax * kmax], rezA[tmax], rezB[tmax][nmax * kmax];
char ch;

void show(int p)
{
	ct++;
	for(int i = 1; i <= bType; i++)
		if(b[i] == ct)
		{
			ram--;
			for(int j = 1; j <= p; j++)
				rezB[i][j] = ax[j];
		}

	for(int i = 1; i <= aType; i++)
	{
		int laFel = 1;
		for(int j = 1; j <= p; j++)
			if(ax[j] != a[i][j])
			{
				laFel = 0;
				break;
			}
		if(laFel) 
		{
			rezA[i] = ct;
			ram--;
		}
	}
}

void back(int p)
{
	for(int i = 1; i <= n; i++)
		if(i != ax[p - 1] && v[i])
		{
			if(!ram) return ;
			ax[p] = i;
			v[i]--;
			if(p == n * k) show(p);
			else back(p + 1);
			if(!ram) return ;
			v[i]++;
		}
}
int main()
{
	freopen("nkperm.in", "r", stdin);
	freopen("nkperm.out", "w", stdout);

	scanf("%d %d %d\n", &n, &k, &t);
	int ultim = 0;
	for(int i = 1; i <= t; i++)
	{
		scanf("%c ", &ch);
		if(ch == 'A')
		{
			aType++;
			for(int j = 1; j <= n * k; j++)
				scanf("%d", &a[aType][j]);
			scanf("\n");
			nextRez[++ultim][0] = 1;
			nextRez[ultim][1] = aType;
		}
		else if(ch == 'B')
		{
			bType++;
			scanf("%d\n", &b[bType]);
			nextRez[++ultim][0] = 0;
			nextRez[ultim][1] = bType;
		}
	}

	ram = aType + bType;

	for(int i = 1; i <= n; i++) v[i] = k;
	back(1);

	for(int i = 1; i <= aType + bType; i++)
		if(nextRez[i][0] == 0)
		{
			for(int j = 1; j <= n * k; j++)
				printf("%d ", rezB[nextRez[ultim][1]][j]);
			printf("\n");
		}
		else
		{
			printf("%d\n", rezA[nextRez[ultim][1]]);
		}

	return 0;
}