Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Arbitrage

104.c

/* Arbitrage */
#include <stdio.h>

int num;

double input[20][20];

void
calc(void)
{
	int len;
	int i,j,k;
	int ini,next;

	int order[20][20][20];	/* Order of currencies to change (finished by -1) */
	double best_change[20][20];	/* Best change between i and j */

	int order2[20][20][20];       /* Copies */
	double best_change2[20][20];  /* Copies */

	for(i=0; i<num; i++) {
		for(j=0; j<num; j++) {
			best_change[i][j]=input[i][j];
			order[i][j][0]=-1;
		}
	}
	for(len=2; len<=num; len++) {
		memcpy(order2, order, sizeof(order));
		memcpy(best_change2, best_change, sizeof(best_change));
		for(i=0; i<num; i++) {
			for(j=0; j<num; j++) {
				for(k=0; k<num; k++) {
					double a;
					int cur_len=0;
					int l;
					cur_len=1;
					for(l=0; order[k][j][l]!=-1; l++) {
						cur_len++;
					}
					if (cur_len >= len) {
						continue;
					}
					a = input[i][k]*best_change[k][j];
					if (a>best_change2[i][j]) {
						best_change2[i][j]=a;
						order2[i][j][0]=k;
						memcpy(&order2[i][j][1], &order[k][j][0],19*sizeof(int));
						if (i==j && a>1.01) {
							ini=i;
							next=k;
							goto yata;
						}
					}
				}
			}
		}
		memcpy(order, order2, sizeof(order));
		memcpy(best_change, best_change2, sizeof(best_change));
#if 0
		printf("\nlen=%d\n", len);
		for(i=0; i<num; i++) {
			for(j=0; j<num; j++) {
				printf("[%d,%d]: (%f): ", i+1, j+1, best_change[i][j]);
				printf("%d ", i+1);
				for(k=0; order[i][j][k]!=-1; k++) {
					printf("%d ", order[i][j][k]+1);
				}
				printf("%d\n", j+1);
			}
		}
#endif
	}
	printf("no arbitrage sequence exists\n");
	return;
yata:
	printf("%d ", ini+1);
	for(i=0; order2[ini][ini][i]!=-1; i++) {
		printf("%d ", order2[ini][ini][i]+1);
	}
	printf("%d\n", ini+1);
	return;
}

int
main(void)
{
	int i,j;

	while(scanf("%d", &num)==1) {
		if (num<2 || num>20) {
			abort();
		}
		for(i=0; i<num; i++) {
			for(j=0; j<num; j++) {
				if (i!=j) {
					scanf("%lf", &input[i][j]);
				}
			}
		}
		for(i=0; i<num; i++) {
			input[i][i]=1.0;
		}
		calc();
	}
	exit(0);
}