#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FILL(a,b) fill(a,a+(sizeof(a)/sizeof(a[0])),b) #define FOR(a,b,c) for(int a=b; a<=c; a++) #define DOWNFOR(a,b,c) for(int a=b; a>=c; a--) #define SIZEOF(a) (sizeof(a)/sizeof(a[0])) #define FORARR(i,a) for(unsigned i=0; i currencyIndexes; deque adj[201]; FOR(i,1,C) { string code; cin >> code; currencyIndexes[code] = nextCurIndex++; } int rates; cin >> rates; FOR(i,1,rates) { string from, to; int fr, tr; char colon; cin >> from >> to >> fr >> colon >> tr; exch e(currencyIndexes[to], (double)fr/tr); adj[currencyIndexes[from]].push_back(e); } double shortestPath[201] = {0}; FOR(v,0,C-1) { if (shortestPath[v] != 0) continue; shortestPath[v] = 1; FOR(i,0,C-1) { bool changed = false; FOR(c,0,C-1) { if (shortestPath[c] == 0) continue; FOREACH(a,adj[c]) { double dcr = shortestPath[a->dest]; if (dcr == 0 || a->rate * shortestPath[c] < dcr) { shortestPath[a->dest] = a->rate * shortestPath[c]; changed = true; } } } if (!changed) break; } FOR(c,0,C-1) { if (shortestPath[c] == 0) continue; FOREACH(a,adj[c]) { double dcr = shortestPath[a->dest]; if (dcr == 0 || a->rate * shortestPath[c] < dcr) { cout << "Arbitrage" << endl; goto out; } } } } cout << "Ok" << endl; out: {} // ********************************************** /* vector currencies; map > adj; FOR(i,1,C) { string code; cin >> code; currencies.push_back(code); } int rates; cin >> rates; FOR(i,1,rates) { string from, to; int fr, tr; char colon; cin >> from >> to >> fr >> colon >> tr; exch e(to, (double)fr / tr); adj[from].push_back(e); } map shortestPath; FOREACH(i,currencies) { shortestPath[*i] = 0; } FOR(v,0,C-1) { if (shortestPath[currencies[v]] != 0) continue; shortestPath[currencies[v]] = 1; FOR(i,1,C) { bool changed = false; FOREACH(c,currencies) { if (shortestPath[*c] == 0) continue; FOREACH(a,adj[*c]) { double dcr = shortestPath[a->destCode]; if (dcr == 0 || a->rate * shortestPath[*c] < dcr) { shortestPath[a->destCode] = a->rate * shortestPath[*c]; changed = true; } } } if (!changed) { break; } } FOREACH(c,currencies) { if (shortestPath[*c] == 0) continue; FOREACH(a,adj[*c]) { double dcr = shortestPath[a->destCode]; if (dcr == 0 || a->rate * shortestPath[*c] < dcr) { cout << "Arbitrage" << endl; goto out; } } } } cout << "Ok" << endl; out: {}*/ } return 0; }