OJ Board

Code: Select all

while( gets(tempA) )
{
       gets(tempB);
}

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int A[10000];
int B[10000];
char *tempA;
char *tempB;
int **LCS_Table;

void Parse_Input(char *temp, int *target, int *length);
void Quicksort(int *A, int p, int r);
int Partition(int *A, int p, int r);
int Find_LCS(int i, int j);
int MAX(int a, int b);

int main()
{
    int lengthA;
    int lengthB;

    tempA = (char *)calloc(sizeof(char), 100);
    tempB = (char *)calloc(sizeof(char), 100);
    while(gets(tempA))
    {
        gets((tempB));
        
        lengthA = 1;
        lengthB = 1;
        Parse_Input(tempA, A, &lengthA);
        Parse_Input(tempB, B, &lengthB);
        lengthA--;
        lengthB--;

        free(tempA);
        free(tempB);
        tempA = (char *)malloc(100 * sizeof(char));
        tempB = (char *)malloc(100 * sizeof(char));

        Quicksort(A, 1, lengthA);
        Quicksort(B, 1, lengthB);
        LCS_Table = (int **)malloc((lengthA + 1) * sizeof(int *));

        int i;
        for(i=0; i<=lengthA; i++)
            LCS_Table[i] = (int *)malloc((lengthB + 1) * sizeof(int));
            
        int j;
        for(i=0; i<=lengthA; i++)
            for(j=0; j<=lengthB; j++)
                LCS_Table[i][j] = -1;

        int a = Find_LCS(lengthA, lengthB);
        
        if(!a)
            printf("A and B are disjoint\n");
        else if(a == lengthA)
        {
            if(a == lengthB)
                printf("A equals B\n");
            else if(a > lengthB)
                printf("B is a proper subset of A\n");
            else
                printf("A is a proper subset of B \n");
        }
        else if(a == lengthB)
        {
            if(a == lengthA)
                printf("A equals B\n");
            else if(a > lengthA)
                printf("A is a proper subset of B \n");
            else
                printf("B is a proper subset of A\n");
        }
        else
            printf("I'm confused!\n");
        

    }

    return 0;
}

void Parse_Input(char *temp, int *target, int *length)
{
    //printf("strlen(temp) = %d\n", strlen(temp));
    temp[strlen(temp)+1] = ' ';
    temp[strlen(temp)+2] = '\0';
    char *pch;
    pch = strtok (temp, " ");
    while (pch != NULL)
    {
        target[*length] = atoi(pch);
        (*length)++;
        //printf ("%s\n",pch);
        pch = strtok(NULL, " ");
    }

}

void Quicksort(int *A, int p, int r)
{
    if(p < r)
    {
        int q = Partition(A, p, r);
        Quicksort(A, p, q);
        Quicksort(A, q+1, r);
    }
}

int Partition(int *A, int p, int r)
{
    int x = *(A+p);
    int i = p - 1;
    int j = r + 1;
    int temp;
    while(1)
    {
        while(1)
        {
            j--;
            if(*(A+j) <= x)
                break;
        }
        while(1)
        {
            i++;
            if(*(A+i) >= x)
                break;
        }
        if(i < j)
        {
            temp = *(A+i);
            *(A+i) = *(A+j);
            *(A+j) = temp;
        }
        else
        {
            return j;
        }
    }
}




int Find_LCS(int i, int j)
{
    if(LCS_Table[i][j] > 0)
        return LCS_Table[i][j];
    else
    {
        if(!i || !j)
            LCS_Table[i][j] = 0;
        else if(A[i] == B[j])
        {
            LCS_Table[i][j] = Find_LCS(i-1, j-1) + 1;
        }
        else
        {
            LCS_Table[i][j] = MAX(Find_LCS(i-1, j), Find_LCS(i, j-1));
        }
            
        return LCS_Table[i][j];
    }
}

int MAX(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}

Code: Select all

Delete after AC

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUF 500
#define equal 1
#define conf 2
#define disj 3
#define B_sub_A 4
#define A_sub_B 5

int compare(const void *a, const void *b)		
{																
	return (*(int*)a - *(int*)b);	
}		
int* removeDuplicates(int* set, int* len)
{
	int i, j;
	int* arr = malloc(sizeof(int)*BUF);
	
	arr[0] = set[0];
	
	for(i=1, j=1;i<*len;i++) {	
		while(set[i] == set[i-1] && i < *len) i++;
		if(i >= *len) break;
		arr[j] = set[i];
		j++;
	}

	*len = j;
	return arr;		
}
int compare_sets(int set_a[], int len_a, int set_b[], int len_b)
{
	int i, j, count;
	
	set_a = removeDuplicates(set_a, &len_a);
	set_b = removeDuplicates(set_b, &len_b);
	
	if(len_a == len_b) {
		count = 0;
		for(i=0; i<len_a; i++) {
			if(set_a[i] == set_b[i]) count++;	
		}
		if(count == len_a) return equal; /* set A equals B */
		else {
			count = 0;
			for(i=0;i<len_a;i++) {
				for(j=0;j<len_b;j++) {	
					if(set_a[i] == set_b[j]) return conf;
				}
			}
		}		
	}
	else if(len_a > len_b) {
		count = 0;
		for(i=0; i<len_b; i++) {
			if(set_a[i] == set_b[i]) count++;	
		}
		if(count == len_b) return B_sub_A; /* B is a proper subset of A */
		else {
			count = 0;
			for(i=0;i<len_a;i++) {
				for(j=0;j<len_b;j++) {	
					if(set_a[i] == set_b[j]) return conf;
				}
			}
		}		
	}
	else {
		count = 0;
		for(i=0; i<len_a; i++) {
			if(set_a[i] == set_b[i]) count++;	
		}
		if(count == len_a) return A_sub_B; /* A is a proper subset of B */
		else {
			count = 0;
			for(i=0;i<len_a;i++) {
				for(j=0;j<len_b;j++) {	
					if(set_a[i] == set_b[j]) return conf;
				}
			}
		}			
	}
	return disj;	
}
int main()
{
	int set1[BUF];
	int set2[BUF];
	char* val, *p;
	int len1, len2, i, isSubSet;
	
	while(1) {
		val = malloc(BUF);	
		if(fgets(val, BUF, stdin)==NULL) break;
		
		p = strtok(val, " ");	
		i = 0;
		while(p) {
			set1[i] = atoi(p);
			p = strtok(NULL, " ");
			i++;
		}
		len1 = i;
		free(val);		
		val = malloc(BUF);			
		fgets(val, BUF, stdin);
		
		p = strtok(val, " ");	
		i = 0;
		while(p) {
			set2[i] = atoi(p);
			p = strtok(NULL, " ");
			i++;
		}
		len2 = i;
		free(val);
		
		qsort (set1, len1, sizeof(int), compare);	
		qsort (set2, len2, sizeof(int), compare);	
		isSubSet = compare_sets(set1, len1, set2, len2);
		
		switch(isSubSet) {
			case equal: printf("A equals B\n");
			break;
			case conf: printf("I'm confused!\n");
			break;
			case disj: printf("A and B are disjoint\n");
			break;
			case A_sub_B: printf("A is a proper subset of B\n");
			break;
			case B_sub_A: printf("B is a proper subset of A\n");
		}		
	}
	
	return 0;
}	

Code: Select all

#include<stdio.h>

int main(){
int asb,bsa,i,j,k,a[50],b[50],l,p,q;
char c;
while(1){
    asb=0;bsa=0;

  for(i=0;;i++) {
    scanf("%d%c",&a[i],&c);
     if(c=='\n')
      break;}

  for(j=0;;j++) {
  scanf("%d%c",&b[j],&c);
  if(c=='\n')
     break;}


p=0;
 for(k=0;k<=i;k++)
    for(l=0;l<=j;l++)
    {
        if(a[k]==b[l])
                   p++;

    }
if(p==i+1)
  asb=1;

q=0;
 for(k=0;k<=j;k++)
   for(l=0;l<=i;l++)
    {
        if(b[k]==a[l])
               q++;

    }

if(q==j+1)
  bsa=1;


if(bsa==1&&asb==1)
 printf("A equals B\n");
else if(bsa==1&&asb==0)
printf("B is a proper subset of A\n");
else if(bsa==0&&asb==1)
printf("A is a proper subset of B\n");
else if(p==0&&q==0)
printf("A and B are disjoint\n");


else printf("I'm confused!\n");

}


return 0;
}