Cod sursa(job #47589)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon 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;
}