Cod sursa(job #23477)

Utilizator devilkindSavin Tiberiu devilkind Data 28 februarie 2007 20:20:33
Problema Amlei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 50
#define TMAX 501

long int a[TMAX][NMAX],b[TMAX][NMAX],n,i,j,k,ord[NMAX],v1[TMAX],v2[TMAX],x1,x2,t,u;
long int val;

FILE *f = fopen("amlei.in","rt"), *g = fopen("amlei.out","wt");

void citire()
{
fscanf(f,"%ld %ld %ld\n",&n,&t,&u);
for (i=1;i<=t;i++)
    {for (j=1;j<=n;j++)
        {fscanf(f,"%ld",&k);
        val=0;
        if (k<0) {val=1;k=k*(-1);}
        a[i][k]=val;
        }
/*    for (j=1;j<=n;j++)
        fprintf(g,"%ld ",a[i][j]);
    fprintf(g,"\n");*/
    }
//fprintf(g,"\n");
for (i=1;i<=u;i++)
    {for (j=1;j<=n;j++)
        {fscanf(f,"%ld",&k);
        val=0;
        if (k<0) {val=1;k=k*(-1);}
        b[i][k]=val;
        }    
/*    for (j=1;j<=n;j++)
        fprintf(g,"%ld ",b[i][j]);   
    fprintf(g,"\n");*/
    }
}

int egal(long int i, long int j,long int ref)
{
long int k=1;
if (ref) {
         while (b[i][k]==b[j][k]&&k<=n)
               k++;
         if (k>n) return 0;
         return b[i][k]-b[j][k];
         }
    else {
         while (a[i][k]==a[j][k]&&k<=n)
               k++;
         if (k>n) return 0;
         return a[i][k]-a[j][k];
         }
    
}

int cmp1(const void *x, const void *y)
{
long int X = * (long int *) x, Y = * (long int *) y;    
return egal(X,Y,0);
}

int cmp2(const void *x, const void *y)
{
long int X = * (long int *) x, Y = * (long int *) y;    
return egal(X,Y,1);
}

int comp(long int i, long int j)
{
long int k=1;
while (a[i][k]==b[j][k]&&k<=n)
               k++;
if (k>n) return 0;
return 1;
}
    


void solve()
{
for (i=1;i<=t;i++)
    ord[i]=i;
qsort(ord,t+1,sizeof(long int),cmp1);
i=1;
x1=0;x2=0;
while (i<=t)
      {
      k=i+1;
      v1[++x1]=ord[i];
      while (egal(ord[i],ord[k],0)==0)
	    k++;
      i=k;
      }

for (i=1;i<=u;i++)
    ord[i]=i;
qsort(ord,u+1,sizeof(long int),cmp2);
i=1;
while (i<=u)
      {
      k=i+1;
      v2[++x2]=ord[i];
      while (egal(ord[i],ord[k],1)==0)
            k++;
      i=k;
      }
      
/*for (i=1;i<=x1;i++)
    fprintf(g,"%ld ",v1[i]);
fprintf(g,"\n");
for (i=1;i<=x2;i++)
    fprintf(g,"%ld ",v2[i]);*/


      
if (x1!=x2) {fprintf(g,"NU\n");return;}
for (i=1;i<=x1;i++)
    if (comp(v1[i],v2[i])==1) {fprintf(g,"NU\n");return;}
fprintf(g,"DA\n");
}

int main()
{
while (!feof(f))
      {
      a[0][1]=-1;
      b[0][1]=-1;
      citire();
      solve();
      fscanf(f,"\n");
      }
fclose(f);
fclose(g);
return 0;
}