At most k exchanges
An exchange office has a board: one unit of currency A buys r units of currency B. Each operation is a separate receipt, and you are willing to make at most k operations. How much of currency T can you get from 1,000,000 units of currency S? Exchanges may be made in any order, through any currencies, including going back to ones already visited.
Input
The first line holds n and m, the number of currencies and the number of lines on the board (1 ≤ n ≤ 300, 1 ≤ m ≤ 6000). Then m lines A B r: currency codes of three capital Latin letters and the rate, a decimal number from 10−6 to 106. The last line holds S, T and k (0 ≤ k ≤ 300).
Output
The largest sum in currency T with a relative error of at most 10−6, or -1 if T cannot be obtained in at most k operations. With k = 0 and S = T the answer is 1,000,000.
Tests 5 to 7 are the reference rates of 9 October 2026 from the article: in the fifth and sixth each operation costs 0.2 %, in the seventh it is the rounded ECB table without a fee.
Examples
Example 1
3 3 AAA BBB 2.000000000 BBB CCC 2.000000000 AAA CCC 3.000000000 AAA CCC 1
3000000.000000
Example 2
3 3 AAA BBB 2.000000000 BBB CCC 2.000000000 AAA CCC 3.000000000 AAA CCC 2
4000000.000000
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
What does Bellman–Ford know after k rounds? Note the words “at most”.
2Hint 2
Within one round, a sum found a moment ago can immediately go into the next exchange. How many operations can then hide in one round?
3The idea
Let bestj[v] be the largest sum in currency v that can be obtained in at most j operations. Then bestj+1[v] = max(bestj[v], the max over board lines u → v of bestj[u] · r). This is a round of Bellman–Ford with multiplication instead of addition and maximum instead of minimum, but with one amendment: the new round reads only the old values. The answer is bestk[T].
4Walkthrough
Before each round copy the array: prev = best[:], and compute improvements from prev. Without the copy, a round in the article on Bellman–Ford guarantees “no less than paths of j edges”, and usually finds more: if the board lines happen to come in a good order, one sum travels a long chain of exchanges in one round. For shortest paths this only speeds things up, but here the number of operations is the very condition. In the first sample one operation gets 3,000,000 units of CCC directly, while a round without the copy manages AAA → BBB → CCC and gives 4,000,000, which is what two operations get, as in the second sample.
Logarithms are not needed here: floating-point multiplication with a relative precision of about 10−16 errs by ~10−13 over 300 steps, far from the tolerance.
On the real rates you can see that the exchange round from the article survives a 0.2 % fee: from 1,000,000 tenge four operations bring back 1,010,071 tenge. And three operations turn the same million tenge into 0.5 % more dollars than a direct exchange.
4+Solution
5Complexity
O(k · m) time and O(n) memory: k rounds over all board lines and two copies of the array of sums.
6Common mistakes
- A round without a copy. The answer on the first sample is 4,000,000 instead of 3,000,000; on the eighth test a chain of 299 exchanges is covered in one round.
- Exactly k operations instead of “at most”. Without taking the maximum with the old value, a sum that is better left alone will be forced to “spend” an extra operation.
- Dijkstra on logarithms. Rates can be greater than one, so logarithms can be negative, and besides, Dijkstra cannot limit the number of steps.