#include #include #include #include #include using namespace std; void clearLocker(bool **locker, int size) { for (int i = 0 ; i < size ; ++i) for (int j = 0 ; j < size ; ++j) locker[i][j]=false; } void clearGraph(float **graph, int size) { for (int i = 0 ; i < size ; ++i) for (int j = 0 ; j < size ; ++j) graph[i][j]=0.0; } float prochazej(float **graph, bool **locker, int size, int pos, int start, float cost, bool first) { float ret = 0.0; if (pos == start && !first) return cost; for (int i = 0 ; i < size ; ++i) { if (i == pos) continue; if (graph[pos][i] != 0.0) if (!locker[pos][i]) { locker[pos][i] = true; ret = max(ret, prochazej(graph, locker, size, i, start, cost*graph[pos][i], false)); // locker[pos][i] = false; } } return ret; } bool hledej(float **graph, bool **locker, int size) { //clearLocker(); // tohle asi nebude potreba for (int i = 0 ; i < size ; ++i) if (prochazej(graph, locker, size ,i, i, 1.0, true) > 1) return true; return false; } int main() { int C = 0; // number of currency int R = 0; // number of exchange rates float **graph = new float *[200]; // double for (int i = 0 ; i < 200 ; ++i ) graph[i] = new float[200]; char c1[3]; char c2[3]; string cs1; string cs2; bool **locker = new bool *[200]; for (int i = 0 ; i < 200 ; ++i ) locker[i] = new bool[200]; int op1, op2; // operands for exchange rate int x,y; // graph souradnice map mapa; // while(1) { scanf("%d", &C); if(C == 0) break; clearGraph(graph, C); clearLocker(locker, C); mapa.clear(); for (int i = 0 ; i < C ; ++i) { scanf("%s", c1); mapa.insert(make_pair( string(c1), i )); } /*map::iterator iter; for( iter = mapa.begin(); iter != mapa.end(); ++iter ) { cout << "Key: '" << iter->first << "', Value: " << iter->second << endl; }*/ // scanf("%d", &R); for (int i = 0 ; i < R ; ++i) { //scanf("%s%s %d:%d", c1, c2, &op1, &op2); /*scanf("%s", c1); scanf("%s", c2); scanf("%d:%d",&op1, &op2);*/ cin >> cs1 >> cs2; scanf("%d:%d",&op1, &op2); x = mapa[cs1]; y = mapa[cs2]; //cout << cs1 << x << " " << cs2 << y << " " << op1 << " " << op2 << endl; graph[x][y] = float(op2) / float(op1); } //cout << endl; if (hledej(graph,locker, C)) printf("Arbitrage\n"); else printf("Ok\n"); /*map::iterator iter; for( iter = mapa.begin(); iter != mapa.end(); ++iter ) { cout << "Key: '" << iter->first << "', Value: " << iter->second << endl; } // cout << endl;*/ } // for (int i = 0 ; i < 200 ; ++i ) delete [] graph[i]; delete graph; // return 0; }