Выгодный круг обменов
Даны курсы обмена: «за x единиц валюты A дают y единиц валюты B». Можно ли, начав с какой-нибудь суммы в какой-нибудь валюте, сделать несколько обменов и вернуться в ту же валюту с большей суммой? Если можно, покажите такой круг.
Курсы целочисленные, и проверка точная: произведение курсов y/x вдоль вашего круга должно быть строго больше единицы. Тесты с 3-го по 6-й — настоящие справочные курсы 9 октября 2026 года, как в статье: курсы тенге Нацбанка, курсы евро ЕЦБ, вместе и по отдельности, и таблица ЕЦБ, пересчитанная к каждой валюте и округлённая.
Вход
В первой строке n и m — число валют и число курсов (2 ≤ n ≤ 200, 1 ≤ m ≤ 6000). Дальше m строк A B x y: коды валют из трёх заглавных латинских букв и два целых числа, 1 ≤ x, y ≤ 3 · 109. Для одной пары валют бывает несколько курсов — годится любой. Гарантируется: если выгодный круг есть, то есть и круг, который увеличивает сумму хотя бы на одну миллионную её часть.
Выход
NO, если выгодного круга нет. Иначе YES и во второй строке коды валют круга по порядку обменов, первая и последняя — одна и та же валюта, например KZT ZAR EUR KZT. Подходит любой выгодный круг.
Примеры
Пример 1
3 4 AAA BBB 1 2 BBB CCC 1 3 CCC AAA 5 1 BBB AAA 2 1
YES AAA BBB CCC AAA
Пример 2
3 4 AAA BBB 1 2 BBB CCC 1 3 CCC AAA 6 1 AAA CCC 1 6
NO
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Произведения неудобны для алгоритмов кратчайших путей. Как превратить произведение курсов в сумму, а «больше единицы» — в «меньше нуля»?
2Подсказка 2
Возьмите −log курса. Выгодный круг — цикл отрицательной длины. Его не обязательно искать из одной валюты: можно начать из всех сразу.
3Подсказка 3
В четвёртом тесте у каждой валюты курс к тенге и обратный к нему, и их произведение ровно 1. Что скажет ваша программа?
4Идея
Положим вес ребра A → B равным log x − log y. Тогда произведение курсов вдоль круга больше единицы ровно тогда, когда сумма весов отрицательна, — это задача поиска отрицательного цикла, и её решает Беллман — Форд. Чтобы найти цикл в любой части графа, а не только достижимый из одной валюты, начинаем со всех вершин сразу: расстояния всех равны нулю, будто есть невидимая валюта, из которой во все ведут рёбра длины 0. Если n-й раунд ещё что-то улучшил, делаем n шагов назад по указателям parent от последней улучшенной вершины — и оказываемся на цикле.
5Разбор
Главная ловушка — точность. Курсы QAR → KZT и KZT → QAR из Нацбанка — это 12 317/100 и 100/12 317, и их произведение ровно 1. Но логарифмы в плавающей точке складываются в −10−16 или +10−16 — как повезёт, — и программа без запаса находит «прибыль» там, где её нет: на четвёртом тесте она отвечает YES и предлагает круг KZT → QAR → KZT. Поэтому улучшение засчитываем, только если оно больше 10−9. Это безопасно: по условию выгодный круг, если он есть, даёт хотя бы 10−6 в логарифмах, и круг из 200 рёбер с потерей не больше 10−9 на каждом ребре его не пропустит.
Можно обойтись и без логарифмов — сравнивать произведения дробей точно, — но числители и знаменатели после двухсот обменов становятся огромными. Логарифмы с запасом проще, и для них достаточно условия о миллионной доле.
На настоящих курсах выходит то же, что в статье. По отдельности Нацбанк и ЕЦБ согласованы: все курсы идут через тенге или через евро, и обойти круг с прибылью нельзя. Вместе они расходятся, и находится круг ZAR → EUR → KZT → ZAR. А округлённая таблица ЕЦБ даёт «прибыль» на одних округлениях: купить рупии за доллары и тут же продать.
5+Решение
6Сложность
O(n · m): не больше n раундов по всем курсам, и раунды прекращаются раньше, если ничего не меняется.
7Типичные ошибки
- Сравнение без запаса. Четвёртый, пятый, седьмой и двенадцатый тесты: точные курсы, а «прибыль» от ошибок округления.
- Поиск только из одной валюты. В седьмом и восьмом тестах выгодный круг может быть недостижим из выбранной валюты.
- Печатать не цикл, а путь к нему. Последняя улучшенная вершина может висеть на хвосте, ведущем к циклу, а не лежать на нём: сначала нужно сделать n шагов назад.
- Дейкстра. Веса отрицательные, и уже обработанная валюта может подешеветь — см. ловушку в статье о Дейкстре.