Cod sursa(job #19486)

Utilizator astronomyAirinei Adrian astronomy Data 19 februarie 2007 17:52:52
Problema Amlei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;

#define MAXN (1 << 15)

typedef long long llong;

int N, A[2][MAXN];
llong P[64];

int ruleaza(int prev, int crt)
{
    int i, j, k;
    llong x;
    set<llong> T;
    
    for(i = j = 1; i <= A[crt][0]; i++)
    {
        for(x = 0, k = 1; k <= N; j++, k++)
         if(A[crt][j] == 1)
            x += P[k-1];
        T.insert(x);
    }

    for(i = j = 1; i <= A[prev][0]; i++)
    {
        for(x = 0, k = 1; k <= N; j++, k++)
         if(A[prev][j] == 1)
            x += P[k-1];
        if( T.find(x) == T.end() )
            return 0;
    }

    return 1;
}

void baga(void)
{
    int i, j, k, t, u, x, L;

    scanf("%d %d %d\n", &N, &t, &u);

    memset(A, 0, sizeof(A));
    
    A[0][0] = t, A[1][0] = u;

    for(i = k = 1; i <= t; i++, k += N)
    {
        for(j = 1; j <= N; j++)
        {
            scanf("%d ", &x);
            if(x > 0)
                A[0][k+x-1] = 1;
        }
    }
    for(i = k = 1; i <= u; i++, k += N)
    {
        for(j = 1; j <= N; j++)
        {
            scanf("%d ", &x);
            if(x > 0)
                A[1][k+x-1] = 1;
        }
    }

    if( (!ruleaza(0, 1)) || (!ruleaza(1, 0)) )
        printf("NU\n");
    else
        printf("DA\n");
}

int main(void)
{
    freopen("amlei.in", "rt", stdin);
    freopen("amlei.out", "wt", stdout);

    int i;

    for(P[0] = 1, i = 1; i <= 52; i++)
        P[i] = P[i-1]*2;
        
    while( !feof(stdin) )
        baga();

    return 0;
}