/*	welfare_crook.c -- Matthias Jauernig, 10.01.04					*/
/*	Programm simuliert das Welfare-Crook-Problem, nach dem der kleinste 		*/
/*	gemeinsame Eintrag dreier Arrays gefunden werden soll				*/

#include <stdio.h>

/* -- Struktur zum Speichern des gemeinsamen Eintrags sowie der Indizes deklarieren ---	*/
typedef struct{
	int kge;	// kge=(k)leinster (g)emeinsamer (E)intrag
	int i1;		// a[i1]=kge, b[i2]=kge, c[i3]=kge;
	int i2;
	int i3;
} rg_struct;

/* -- welfare_crook() -- ermittelt den kleinsten gemeinsamen Eintrag der 3 Arrays -----	*/
rg_struct welfare_crook(int *a, int *b, int *c, int l1, int l2, int l3){
	int i, j, k, gef=0;
	rg_struct erg={-1,-1,-1,-1};
	//solange kein gemeinsamer Eintrag gefunden (gef=0) und eines alle drei
	//Arrays ihre Grenze nicht überschritten haben...
	for(i=0, j=0, k=0; !gef && i<l1 && j<l2 && k<l3; i++){
		while(b[j]<a[i]) j++;//geht zu nächstem relevanten Index j von b
		while(c[k]<a[i]) k++;//geht zu nächstem relevanten Index k von c

		if(a[i]==b[j] && a[i]==c[k]){//wenn drei Elemente gleich -> abspeichern
			erg.kge=a[i];
			erg.i1=i;
			erg.i2=j;
			erg.i3=k;
			gef=1;//Abbruchbedingung erfüllen
		}
	}
	return erg;
}

/* ---- main() ------------------------------------------------------------------------	*/
int main(void){
	int a[]={1,3,4,7,8,11,13,15,16,17,20};//Beispielarrays initialisieren
	int b[]={2,5,13,15,16,18,20};
	int c[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	int l1=sizeof(a)/sizeof(a[0]);//Anzahl der Elemente der Arrays a,b,c bestimmen
	int l2=sizeof(b)/sizeof(b[0]);
	int l3=sizeof(c)/sizeof(c[0]);
	int i;
	rg_struct erg=welfare_crook(a,b,c,l1,l2,l3);

	printf(	"\nWelfare-Crook-Problem\n"
		"---------------------\n\n");
	printf("Gegeben seien folgende drei Arrays:\n");
	printf(" a[]:  ");
	for(i=0; i<l1; i++)
		printf("%d, ", a[i]);
	printf("\b\b \n b[]:  ");
	for(i=0; i<l2; i++)
		printf("%d, ", b[i]);
	printf("\b\b \n c[]:  ");
	for(i=0; i<l3; i++)
		printf("%d, ", c[i]);
	printf("\b\b \n\n");

	printf("Lösung des Welfare-Crook-Problems:\n");
	if(erg.i1==-1) printf("Kein gemeinsamer Eintrag vorhanden!\n\n");
	else{
		printf(	" kleinster gemeinsamer Eintrag: %d\n", erg.kge);
		printf(	" Stellen dessen Vorkommens: a[%d], b[%d], c[%d]\n\n",
			erg.i1, erg.i2, erg.i3);
	}

	return 0;
}
/* Ausgabe für die Beispielarrays:
Welfare-Crook-Problem
---------------------

Gegeben seien folgende drei Arrays:
 a[]:  1, 3, 4, 7, 8, 11, 13, 15, 16, 17, 20
 b[]:  2, 5, 13, 15, 16, 18, 20
 c[]:  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Lösung des Welfare-Crook-Problems:
 kleinster gemeinsamer Eintrag: 13
 Stellen dessen Vorkommens: a[6], b[2], c[12]
*/