img
Czech ACM Student Chapter
Czech Technical University in Prague
acm
Charles University in Prague
Technical University of Ostrava
cz
Slovak University of Technology
Masaryk University
ˇ
ˇ ´
University of Zilina
Pavol Jozef Safarik University in Koˇice
s
CTU Open Contest 2010
Arbitrage?
arbitrage.c, arbitrage.C, arbitrage.java, arbitrage.p
If you are going to travel to the World Finals, you cannot rely on Czech Crowns. You would
have to exchange your money for various foreign currencies. This problem deals with multiple
currencies and their exchange rates. Your task is to verify that some set of exchange rates is
safe, namely detect a possibility of so-called arbitrage.
An arbitrageis a risk-free combination of buy and sell operations that gains profit from im-
balance in market prices. The prices may apply to various things, typically stock exchange but
also currencies.
Input Specification
The input consists of several test cases. Each case begins with a line containing one positive
integer number C , 1 C 200, the number of currencies.
The second line of each test case contains C currency codes separated by a space. Each code is
composed of 3 uppercase letters and all codes in one test case are different.
The third line contains one integer number R, 0 R C · (C - 1), the number of exchange
rates available. Each of the following R lines contains one exchange rate in the following format:
first currency code, space, second currency code, space, integer number Ai, colon (":"), and
integer number Bi. The meaning is as follows: If you pay Ai units of the first currency, you will
get Bi units of the second currency. You may assume that 1 Ai, Bi 100 and that the two
currencies are different.
Output Specification
For each test case, print one line of output. If there exists any possible sequence of currency
exchange operations that would result in a profit, the line should contain the word "Arbitrage".
Otherwise, simply print "Ok".
The word profit in this case means that you start with any amount of any currency and after
performing any number of exchanges you will have strictly higher amount of the same currency.
Be careful and do not confuse "arbitrage" with "arbitration", which is something completely different; al-
though the Czech language uses the same word for both.
Sample Input
2
CZK
EUR
2
CZK
EUR 25:1
EUR
CZK 1:25
2
GBP
USD
2
USD
GBP 8:5
GBP
USD 5:9
3
BON
DEM CZK
3
DEM
BON 1:6
BON
CZK 1:5
DEM
CZK 1:20
3
CZK
EUR GBP
3
CZK
EUR 24:1
EUR
GBP 5:4
GBP
CZK 1:30
3
CZK
USD GBP
4
CZK
USD
28:1
CZK
GBP
31:1
GBP
CZK
1:31
USD
GBP
1:1
0
Output for Sample Input
Ok
Arbitrage
Ok
Ok
Arbitrage