Cod sursa(job #28768)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 8 martie 2007 11:32:26
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
# include <stdio.h>
# include <string.h>

# define  _fin  "amlei.in"
# define  _fout "amlei.out"

# define  maxn  52
# define  maxt  502


typedef struct form
{
	int a[maxt], s;
}	form;

form a[maxt], b[maxt], aux;
int n, t, u, sa, sb, sol, oa[maxt], ob[maxt];
int B[maxn];
FILE *fin;


void intercl(int l, int r, int A[])
{
	if (l==r) return;
	int m = (l+r) >> 1, i, j, k;
	intercl(l, m, A), intercl(m+1, r, A);
	for (i=l, j=m+1, k=l; i<=m || j<=r; )
		B[ k++ ] = A[ j>r || (i<=m && A[i]<A[j]) ? i++ : j++ ];
	for (k=l; k<=r; k++) A[k] = B[k];
}

int search(form x, form a[], int r)
{
	int i, j, ok;
	
	for (i=1; i<=r; i++)
		if ( a[i].s==x.s ) {
			for (j=ok=1; j<=n && ok; j++) ok = (a[i].a[j]==x.a[j]);
			if ( ok ) return 1;
		}
	
	return 0;
}

int _search(form x, int l, int r)
{
	int i, j, ok;
	
	for (i=l; i<=r; i++)
	{
		for (j=ok=1; j<=n && ok; j++) ok = (b[ ob[i] ].a[j]==x.a[j]);
		if ( ok ) return 1;
	}
	return 0;
}

void builds(form &x)
{
	int i;
	for (x.s=0, i=1; i<=n; i++)
		x.s = (x.s + x.a[i] * (x.a[i]<0 ? 6666 : 313) );
}

void readf()
{
	int i, j;
	
	fscanf(fin, "%d%d%d", &n, &t, &u);
	if ( feof(fin) ) return;
	
	for (sa=sb=0, i=1; i<=t; i++) {
		for (aux.s=0, j=1; j<=n; j++) fscanf(fin, "%d", &aux.a[j]); // , aux.s += aux.a[j];
		builds(aux);
		
		intercl(1, n, aux.a);
		if ( !search(aux, a, sa) ) a[ ++sa ] = aux;
	}

	for (i=1; i<=u; i++) {
		for (aux.s=0, j=1; j<=n; j++) fscanf(fin, "%d", &aux.a[j]);//, aux.s += aux.a[j];
		builds(aux);

		intercl(1, n, aux.a);
		if ( !search(aux, b, sb) ) b[ ++sb ] = aux;
	}
}

void solve()
{
	// sort a & b by sums
	int i, j, hs, ts, sw;
	
	if ( sa!=sb ) { sol=0; return; }
	
	for (i=1; i<=sa; i++) oa[i]=ob[i]=i;
	
	for (i=1; i<sa; i++)
		for (j=i+1; j<=sa; j++)
			if ( a[ oa[i] ].s > a[ oa[j] ].s ) sw=oa[i], oa[i]=oa[j], oa[j]=sw;
	
	for (i=1; i<sb; i++)
		for (j=i+1; j<=sb; j++)
			if ( b[ ob[i] ].s > b[ ob[j] ].s ) sw=ob[i], ob[i]=ob[j], ob[j]=sw;
	
	if ( a[oa[1]].s==b[ob[1]].s )
	{
		for (hs=ts=1; b[ ob[ts] ].s==b[ ob[hs] ].s && ts<=sb; ++ts);
		
		for (i=sol=1; i<=sa && sol; i++)
		{
			if ( a[ oa[i] ].s > b[ ob[hs] ].s ) {
				if ( b[ ob[ts] ].s != a[ oa[i] ].s || ts>sb ) {
					sol=0; break;
				}
				else for (hs=ts; b[ ob[ts] ].s==b[ ob[hs] ].s && ts<=sb; ++ts);
			}
			
			sol = _search(a[ oa[i] ], hs, ts-1);
		}
	}
	else sol=0;
}

int main()
{
	fin=fopen(_fin, "r");
	freopen(_fout,"w", stdout);
	
	while ( 1 )
	{
		readf();
		if ( feof(fin) ) break;
		solve();
		printf("%s\n", sol?"DA":"NU");
	}
	
	return 0;
}