Cod sursa(job #71463)

Utilizator c_sebiSebastian Crisan c_sebi Data 10 iulie 2007 17:00:05
Problema Amlei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIM 510

FILE *f = fopen("amlei.in", "r");
FILE *g = fopen("amlei.out", "w");

int a[DIM][51], b[DIM][51];
int n, t, u;
char A[DIM][200], B[DIM][200];

void quick (int x[], int st, int dr) {
	int i, ii, j, jj, aux;
	i=st; j=dr;
	ii=0; jj=-1;
	if (st<dr){
		while (i<j) {
			if (x[i]>x[j]) {
				aux=x[i]; x[i]=x[j]; x[j]=aux;
				aux=-ii; ii=-jj; jj=aux;
			}
			i=i+ii;
			j=j+jj;
		}
	quick(x, st, i-1);
	quick(x, i+1, dr);
	}
}

void quick2 (char x[][200], int st, int dr) {
	int i, ii, j, jj, aux;
	char aux2[200];
	i=st; j=dr;
	ii=0; jj=-1;
	if (st<dr){
		while (i<j) {
			if (strcmp(x[i], x[j])>0) {
				strcpy(aux2, x[i]); strcpy(x[i], x[j]); strcpy(x[j], aux2);
				aux=-ii; ii=-jj; jj=aux;
			}
			i=i+ii;
			j=j+jj;
		}
	quick2(x, st, i-1);
	quick2(x, i+1, dr);
	}
}


void read (int a[][51], int t) {
	int j, i;
	for (j = 0; j < t; ++j) {
		for (i = 0; i < n; ++i) {
			fscanf(f, "%d", &a[j][i]);
		}
		quick(a[j], 0, n-1);
	}
}

void convert (int a[][51], char A[][200], int lin) {
	int j, i;
	char s[50];
	for (j = 0; j < lin; ++j)
		for (A[j][0]=0, i=0; i < n; ++i)
			strcat(A[j], itoa(a[j][i], s, 10));
}

void collapse(char A[][200], int &lin) {
	int i, j, k;
	char aux[500];
	for (i = 0; i < lin-1; ++i) {
		if (!strcmp(A[i], A[i+1])) {
			j=i+1;
			while (j<lin && !strcmp(A[i], A[j])) j++;
			for (k=j; k < lin; ++k)
				strcpy(A[i+k-j+1], A[k]);
			lin-=(j-i-1);
		}
	}
}


int eval(){
	int i;
	for (i=0; i<t; ++i)
		if (strcmp(A[i], B[i]))
			return 0;
	return 1;
}


int main() {
	int ech;
	while (fscanf(f, "%d %d %d", &n, &t, &u)==3) {
		read(a, t); read(b, u);
		convert(a, A, t); convert(b, B, u);
		quick2 (A, 0, t-1); quick2(B, 0, u-1);
		collapse(A, t); collapse(B, u);
		if (t!=u) ech=0;
		else ech = eval();
		if (ech) fprintf(g, "DA\n");
		else fprintf(g, "NU\n");
	}
	fclose(f);
	fclose(g);
	return 0;
}