#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 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); } /*#ifdef DEBUG FOREACH(i,adj) { printf("from %s to...\n", i->first.c_str()); FOREACH(a,i->second) { printf(" %s for %f\n", a->destCode.c_str(), a->rate); } } #endif*/ 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; }