home | new paste

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <malloc.h>
#define FL __FILE__,__LINE__
#define PD printf("."); fflush(stdout)
#define tz(x) if(x){printf("\n%s:%d:5:Fail: %s is %d not zero.",FL,#x,x);}else PD;
#define tde(x,y) if(x!=y){printf("\n%s:%d:6:Fail: %s is %d not %d.",FL,#x,x,y);}else PD;
#define tse(x,y) if(strcmp(x,y)){printf("\n%s:%d:6:Fail: %s is %s not %s",FL,#x,x,y);}else PD;

typedef struct entry_t {
	int value;
	int used;
	struct entry_t *next;
} entry;
entry *heada=NULL;
entry *headb=NULL;
void append(int value, entry **tail) {
	if (tail == NULL) {
		return;
	}
	if (*tail == NULL) {
		*tail = calloc(sizeof(entry),1);
		(*tail)->value = value;
		(*tail)->used = 0;
	}else append(value, &(*tail)->next);
}
void print_list(entry *head) {
	entry *current = head;
	while (current != NULL) {
		if( current -> used == 0)
			printf("%d ", current->value);
		else
			printf("x ");
		current = current->next;
	}
	printf("\n");
}
entry *nextunused(entry *head) {
	entry *current = head;
	while (current != NULL) {
		if (current->used == 0) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}
entry *smallestunused(entry *head) {
	entry *current = head;
	int largest = INT_MAX;
	entry *r = NULL;
	while (current != NULL) {
		if (current->used == 0) {
			if (current->value < largest) {
				largest = current->value;
				r = current;
			}
		}
		current = current->next;
	}
	return r;
}

int calcpair() {
	entry *a = smallestunused(heada);
	entry *b = smallestunused(headb);
	if (a == NULL || b == NULL) {
		return 0;
	}
	a->used = 1;
	b->used = 1;
	return abs(a->value - b->value);
}
int allpairs() {
	int sum = 0;
	while(nextunused(heada) != NULL && nextunused(headb) != NULL) {
		sum += calcpair();
	}
	return sum;
}

void readentry(const char *in) {
	int a,b = 0;
	if (in == NULL)
		scanf("%d %d",&a,&b);
	else
		sscanf(in,"%d %d",&a,&b);
	if( a == 0 || b == 0) return;
	append(a,&heada);
	append(b,&headb);
}
void loadtestdata(void){
	heada = NULL;
	headb = NULL;
	readentry("3   4");
	readentry("4   3");
	readentry("2   5");
	readentry("1   3");
	readentry("3   9");
	readentry("3   3");
}
void loadtestdata2(void){
	heada = NULL;
	headb = NULL;
	readentry("3   4");
	readentry("4   4");
	readentry("2   5");
	readentry("1   3");
	readentry("3   9");
	readentry("3   3");
}
void test(void){
	loadtestdata();
	print_list((heada));
	print_list((headb));
	tde(allpairs(),11);
	print_list((heada));
	print_list((headb));
	loadtestdata();
	print_list((heada));
	print_list((headb));
	tde(allpairs(),11);
	tde(allpairs(),0);
	loadtestdata2();
	tde(allpairs(),12);
	heada = NULL;
	headb = NULL;
}
int main() {
	test();
	while(!feof(stdin)) readentry(NULL);
	printf("\nAnswer: %d\n",allpairs());
	return 0;
}