#include #include #include #include #define NUM_CCIES 200 using namespace std; struct Neighbours { int count; int ccies[NUM_CCIES]; }; struct Rate { long from, to; Rate operator *( const Rate &r) const { Rate ret; ret.from = from * r.from; ret.to = to * r.to; return ret; } bool operator != ( const Rate &r)const { return from * r.to != r.from * to; } }; Neighbours neighbours[NUM_CCIES]; Rate rates[NUM_CCIES][NUM_CCIES]; Rate value[NUM_CCIES]; bool arbitrage_found(int from, int to) { // printf("from: %d, value: %ld / %ld\n", from, value[from].from, value[from].to); // printf("to: %d, value: %ld / %ld\n", to, value[to].from, value[to].to); if (value[to].from > 0) { if ( value[from] * rates[from][to] != value[to] ) return true; return false; } value[to] = value[from] * rates[from][to]; Neighbours &neigh = neighbours[to]; for ( int i=0; i ccyind; scanf("%d", &N); if (N==0) break; for ( int i=0; isecond; int ind2=ccyind.find(ccy2)->second; rates[ind1][ind2].from=val1; rates[ind1][ind2].to=val2; Neighbours &neigh1 = neighbours[ind1]; neigh1.ccies[neigh1.count++]=ind2; } if (notfirst) printf("\n"); notfirst=1; memset(value,0,sizeof(value)); value[0].from=value[0].to=1; Neighbours &neigh = neighbours[0]; int i; for ( i=0; i