Cod sursa(job #18509)

Utilizator devilkindSavin Tiberiu devilkind Data 18 februarie 2007 12:30:00
Problema Amlei Scor 60
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasa a 10-a Marime 2.05 kb
#include <stdio.h>
#include <string.h>
#include <math.h>
#define NMAX 128
#define EMAX 512
#define modulo 6613

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

struct hash{long int v[NMAX],poz;
            hash *urm;} *vf[modulo];
            
            
long int t,n,u,i,j,k,h[EMAX],x,v[NMAX],val,fnd[EMAX];     


void init()
{
hash *p,*p1;
for (i=0;i<=modulo-1;i++)    
    {p=vf[i];
    p1=vf[i];
    while (p1)
          {p1=p1->urm;
          p=p1;
          delete p;}
    }  
for (i=0;i<=modulo;i++)    
    vf[i]=NULL;
}

int egal(hash *p)
{
for (i=0;i<=n+51;i++)
    if (v[i]!=p->v[i]) return 0;
return 1;
}

long int abs(long int x)
{
if (x<0) return (-1)*x;
return x;
}

void solve()
{
long int ok,sol=0;
fscanf(f,"%ld %ld %ld",&n,&t,&u);

hash *p;
memset(h,0,sizeof(h));
memset(fnd,0,sizeof(h));

for (k=1;k<=t;k++)
    {
    memset(v,0,sizeof(v));

    for (j=1;j<=n;j++)
	{
	fscanf(f,"%ld",&x);
	x+=51;
	v[x]=1;
	val=(val*abs(x))%modulo;
	}

    p=vf[val];
    ok=0;
    while (p)
	  {
	  if (egal(p)) {ok=1;break;}
	  p=p->urm;
	  }

    if (!ok) {
	     p=new hash;
	     for (i=0;i<=n+51;i++)
		 p->v[i]=v[i];
	     p->poz=k;
	     h[k]=1;
	     p->urm=vf[val];
	     vf[val]=p;
	     }
    }

for (k=1;k<=u;k++)
    {
    memset(v,0,sizeof(v));
    
    for (j=1;j<=n;j++)
        {
        fscanf(f,"%ld",&x);
        x+=51;
        v[x]=1;
        val=(val*abs(x))%modulo;
        }
    if (!sol)
    {
    p=vf[val];
    ok=0;
    while (p)
	  {
	  if (egal(p)) {ok=1;break;}
	  p=p->urm;
	  }

    if (ok) fnd[p->poz]=1;
       else {fprintf(g,"NU\n");
            fscanf(f,"\n");
            sol=1;}
    }
    }    

if (!sol)
{
for (i=1;i<=t;i++)
    if (h[i]!=fnd[i]) {fprintf(g,"NU\n");
                      fscanf(f,"\n");
                      return;}
fprintf(g,"DA\n");
fscanf(f,"\n");
}

}

int main()
{
while (!feof(f))
      {
      init();
      solve();
      }
fclose(f);
fclose(g);
return 0;
}