Trading of one currency for another with the hopes of
taking advantage of small differences in conversion rates among
several currencies in order to achieve a profit. For example, if
1.00 in U.S. currency buys 0.7 British pounds currency, 1.00 in British
currency buys 9.5 French francs, and 1 French franc buys 0.16 in
U.S. dollars, then a forex trader can start with 1.00 USD and earn
1 * 0.7 * 9.5 * 0.16 = 1.064 dollars thus earning a profit of 6.4 percent.
The problem consist to write a program that determines whether a sequence of
currency exchanges can yield a profit as described above.
To result in successful trade, a sequence of exchanges must begin
and end with the same currency, but any starting currency may be
considered.
The input file consists of one or more conversion tables. You must
solve the trading problem for each of the tables in the input file.
Each table is preceded by an integer n on a line by itself giving
the dimensions of the table. The maximum dimension is 20. The minimum
dimension is 2.
The table then follows in row major order but with the diagonal
elements of the table missing (these are assumed to have value 1.0).
Thus the first row of the table represents the conversion rates
between country 1 and n - 1 other countries, i.e. the amount of
currency of country i constrained to 2 eq i eq n that can be purchased with one
unit of the currency of country 1.
Thus each table consists of n + 1 lines in the input file: 1 line
containing n and lines representing the conversion table.
Output
For each table in the input file, you must determine whether a
sequence of exchanges exists that results in a profit of more than 1
percent (0.01). If a sequence exists you must print the sequence of
exchanges that results in a profit. If there is more than one
sequence that results in a profit of more than 1 percent you must
print a sequence of minimal length, i.e. one of the sequences that
uses the fewest exchanges of currencies to yield a profit.
Because the IRS (United States Internal Revenue Service) taxes long
transaction sequences with a high rate, all profitable sequences must
consist of n or fewer transactions where n is the dimension of
the table giving conversion rates. The sequence 1 2 1 represents
two conversions.
If a profitable sequence exists you must print the sequence of
exchanges that results in a profit. The sequence is printed as a
sequence of integers with the integer i representing the i-th line
of the conversion table (country i). The first integer in the
sequence is the country from which the profitable sequence starts.
This integer also ends the sequence.
If no profiting sequence of n or fewer transactions exists, then the line
For a given problem, the conversion table corresponds to a graph and the solution corresponds to a shortest profitable cycle in that graph.
Consider the following conversion table over USD, MXN, and EUR.
When we interpret the conversion table, we write 0 for the rates in the diagonal to indicate that we do not consider edges that start and end in the same vertex.
The reason is that those edges are redundant.
A lasso is an edge that starts and ends in the same vertex.
Lassos are redundant because from a given sequence that includes a lasso you obtain a shorter sequence with the same rate by removing the lasso.
For example, sequence USD USD EUR USD yields profit 1.01, the same profit that the shorter sequence USD EUR USD yields.
A sequence of exchanges may yield a profit only if the sequence is a cycle.
For example, the cycle USD -> MXN -> EUR -> USD yields profit of 1.01^{3/2}.
Given that the number of vertices in the graph is 3, we do not consider cycles longer than 3.
Consider the cycles of length 3 or less.
A cycle is profitable when its rate is greater or equal to 1.01.
Out of the five cycles, only the following two are profitable.
USD -> EUR -> USD
USD -> MXN -> EUR -> USD
Out of the two profitable cycles, USD -> EUR -> USD is the only solution because it is the shortest cycle.
A solution may not be a simple cycle like in the previous example.
For example, consider the following conversion table and its corresponding graph.
4
1 0 0
1.005 0 0
0 0 0
0 0 0
For the graph, the cycles of length 4 or less are the following
CYCLE : RATE
1 2 1 : 1.005
1 2 1 2 1 : 1.010025
The only profitable cycle is 1 2 1 2 1 and therefore it is the only solution.
The cycle is a solution regardless of the fact that it consists of the repetition of simple cycle 1 2 1.
A solution that is not a simple cycle is not necessarily the repetition of a simple cycle like in the previous example.
For example, consider the following conversion table and its corresponding graph.
