n залов с номерами от 0 до n - 1; links[i] = [a, b] — проход между залами a и b. В каждом зале стоят ворота, и при первом их открытии срабатывает значение gates[i]: если оно положительное, открывший получает награду, если отрицательное — платит столько за открытие.
Исследователь стартует в зале 0, соперник — в зале rival. Каждую секунду оба переходят в соседний зал. Исследователь сам выбирает путь от зала 0 к какому-нибудь листу (залу, кроме 0, у которого только один сосед) и, дойдя до листа, останавливается. Соперник идёт кратчайшим путём к залу 0 и останавливается там.
В каждом зале на своём пути участник открывает ворота:
- если ворота уже открыты, ничего не происходит;
- если оба оказались в зале в одну и ту же секунду, они делят значение пополам: на долю исследователя приходится gates[i] / 2, округлённое вниз (например, 7 → 3, -7 → -4).
Стартовые залы открываются в секунду 0. Верните наибольший итоговый доход исследователя при лучшем выборе листа (он может быть отрицательным).links=[[0, 1], [0, 2], [2, 3], [2, 4]], rival=4, gates=[2, -6, 8, 10, -4] → 16
В секунду 0 исследователь открывает ворота 0 (+2), соперник — ворота 4. В секунду 1 оба приходят в узел 2 и делят награду: +4. Дальше выгоднее идти в лист 3: +10. Итого 2 + 4 + 10 = 16. Путь в лист 1 дал бы только 2 - 6 = -4.
links=[[0, 1], [1, 2]], rival=2, gates=[-4, 6, 20] → -1
Соперник открывает ворота 2 в секунду 0 и ворота 1 в секунду 1 — исследователь приходит туда одновременно с ним и получает половину, 3. В лист 2 он приходит, когда ворота уже открыты. Итого -4 + 3 = -1.
links=[[1, 0]], rival=1, gates=[-2, 8] → -2
links задаёт деревоlinks=[[0, 1], [0, 2], [2, 3], [2, 4]], rival=4, gates=[2, -6, 8, 10, -4]
16
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 42 теста на сервере, включая скрытые.