Cod sursa(job #47589)
Utilizator | Data | 3 aprilie 2007 20:19:48 | |
---|---|---|---|
Problema | Amlei | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 5.17 kb |
// Problema amlei
#include <stdio.h>
#define MAX 51
struct Perm
{
int a[MAX];
Perm *next;
};
int pozitie( int st, int dr, int a[MAX] )
{
int piv = a[st];
int i = st-1, j = dr+1;
int aux;
do{
do{ i++; }while( a[i] < piv );
do{ j--; }while( a[j] > piv );
if( i < j )
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}while( i < j );
return j;
}
int qs( int st, int dr, int a[MAX] )
{
if( st == dr ) return 0;
int m = pozitie( st, dr, a );
qs( st, m, a );
qs( m+1, dr, a );
return 0;
}
int compara( int a[MAX], int b[MAX] )
{
for( int i =0; i<=a[0]; i++ )
if( a[i] != b[i] ) return 0;
return 1;
}
int main()
{
freopen( "amlei.in", "rt", stdin );
freopen( "amlei.out", "wt", stdout );
Perm *e, *f, *l1, *l2;
int n, t, u, i;
int a[MAX];
int cd;
while( !feof( stdin ) )
{
scanf( "%d %d %d", &n, &t, &u );
if( feof( stdin ) ) break;
l1 = NULL;
l2 = NULL;
while( t )
{
t--;
for( i=1; i<=n; i++ )
scanf( "%d", &a[i] );
a[0] = n;
qs( 1, n, a );
e = l1;
while( ( e != NULL ) && ( e->a[1] < a[1] ) )
{ f = e; e = e->next; }
if( e!= NULL ) cd = compara( a, e->a ); else cd = 0;
if( !cd )
if( e == l1 )
{
e = new Perm;
for( i=0; i<=n; i++ ) e->a[i] = a[i];
e->next = l1;
l1 = e;
}
else
{
e = new Perm;
for( i=0; i<=n; i++ ) e->a[i] = a[i];
e->next = f->next;
f->next = e;
}
}
while( u )
{
u--;
for( i=1; i<=n; i++ )
scanf( "%d", &a[i] );
a[0] = n;
qs( 1, n, a );
e = l2;
while( ( e != NULL ) && ( e->a[1] < a[1] ) )
{ f = e; e = e->next; }
if( e != NULL ) cd = compara( a, e->a ); else cd = 0;
if( !cd )
if( e == l2 )
{
e = new Perm;
for( i=0; i<=n; i++ ) e->a[i] = a[i];
e->next = l2;
l2 = e;
}
else
{
e = new Perm;
for( i=0; i<=n; i++ ) e->a[i] = a[i];
e->next = f->next;
f->next = e;
}
}
e = l1;
f = l2;
while( ( e != NULL ) && ( f != NULL ) )
{
cd = compara( e->a, f->a );
if( !cd ) break;
e = e->next;
f = f->next;
}
if( ( cd ) && ( e == NULL ) && ( f == NULL ) ) printf( "DA\n" );
else printf( "NU\n" );
}
fclose( stdin );
fclose( stdout );
return 0;
}