Не больше k обменов
В обменном пункте висит табло: за одну единицу валюты A дают r единиц валюты B. Каждая операция — отдельный чек, и вы готовы сделать не больше k операций. Сколько валюты T можно получить из 1 000 000 единиц валюты S? Менять можно в любом порядке, через любые валюты, в том числе возвращаться к уже пройденным.
Вход
В первой строке n и m — число валют и число строк табло (1 ≤ n ≤ 300, 1 ≤ m ≤ 6000). Дальше m строк A B r: коды валют из трёх заглавных латинских букв и курс — десятичное число от 10−6 до 106. В последней строке S, T и k (0 ≤ k ≤ 300).
Выход
Наибольшую сумму в валюте T с относительной погрешностью не больше 10−6 или -1, если не больше чем за k операций получить T нельзя. При k = 0 и S = T ответ — 1 000 000.
Тесты с 5-го по 7-й — справочные курсы 9 октября 2026 года из статьи: в пятом и шестом с каждой операции берут 0,2 %, в седьмом — округлённая таблица ЕЦБ без комиссии.
Примеры
Пример 1
3 3 AAA BBB 2.000000000 BBB CCC 2.000000000 AAA CCC 3.000000000 AAA CCC 1
3000000.000000
Пример 2
3 3 AAA BBB 2.000000000 BBB CCC 2.000000000 AAA CCC 3.000000000 AAA CCC 2
4000000.000000
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Что знает Беллман — Форд после k раундов? Обратите внимание на слово «не больше».
2Подсказка 2
Внутри одного раунда сумма, найденная минуту назад, может тут же пойти в следующий обмен. Сколько тогда операций прячется в одном раунде?
3Идея
Пусть bestj[v] — наибольшая сумма в валюте v, которую можно получить не больше чем за j операций. Тогда bestj+1[v] = max(bestj[v], max по строкам табло u → v из bestj[u] · r). Это раунд Беллмана — Форда с умножением вместо сложения и максимумом вместо минимума, но с одной поправкой: новый раунд читает только старые значения. Ответ — bestk[T].
4Разбор
Перед каждым раундом копируем массив: prev = best[:], и улучшения считаем от prev. Без копии раунд в статье о Беллмане — Форде гарантирует «не меньше, чем пути из j рёбер», и обычно находит больше: если строки табло идут удачно, одна сумма за раунд проходит длинную цепочку обменов. Для кратчайших путей это только ускоряет дело, а здесь число операций — само условие. В первом примере за одну операцию можно получить 3 000 000 единиц CCC напрямую, а раунд без копии успевает сделать AAA → BBB → CCC и выдаёт 4 000 000 — столько получается за две операции, как во втором примере.
Логарифмы здесь не нужны: умножение в плавающей точке с относительной точностью около 10−16 на 300 шагах ошибается на ~10−13, далеко от допуска.
На настоящих курсах видно, что круг обмена из статьи переживает комиссию 0,2 %: из 1 000 000 тенге за четыре операции можно вернуть 1 010 071 тенге. А за три операции из того же миллиона тенге получается на 0,5 % больше долларов, чем при прямом обмене.
4+Решение
5Сложность
O(k · m) времени и O(n) памяти: k раундов по всем строкам табло и две копии массива сумм.
6Типичные ошибки
- Раунд без копии. Ответ на первом примере — 4 000 000 вместо 3 000 000; на восьмом тесте цепочка из 299 обменов проходится за один раунд.
- Ровно k операций вместо «не больше». Если не брать максимум со старым значением, сумма, которой лучше не трогать, обязательно «потратит» лишнюю операцию.
- Дейкстра по логарифмам. Курсы бывают больше единицы, логарифмы — отрицательными, и к тому же Дейкстра не умеет ограничивать число шагов.