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 arbitrage∗ is 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