/¯
Если отрицательные то можем гонять по кругу, не?
если отрицательные, беллмана-форда запускаем и отрицательные циклы чекаем
Size: a a a
2020 April 24
EZ
если отрицательные, беллмана-форда запускаем и отрицательные циклы чекаем
Ну если а отрицательное то очевидно есть отрицательный цикл
/¯
(насчёт b не уверен)
тоже, либо в цикл уперёмся, либо в петлю
V🇺
не сказано, что a и b неотрицательные
если есть отрицательный вес, то ответ, очевидно, -infinity
EZ
тоже, либо в цикл уперёмся, либо в петлю
А ну да, тупанул
KK
если есть отрицательный вес, то ответ, очевидно, -infinity
Это если b отрицательное
KK
Если a - далеко не факт
V🇺
Это если b отрицательное
если a отрицательное - тоже
KK
б - овердофига, вес а -1
/¯
б - овердофига, вес а -1
ну и бегай по кругу по x+1 mod M, кто мешает
KK
ну и бегай по кругу по x+1 mod M, кто мешает
Как ты перепрыгивать через ответ будешь?
KK
Только квадратом
V🇺
б - овердофига, вес а -1
наберем минус единичкими -овердофига*M*овердофига
KK
А квадрат дает за цикл больше, чем единички забирают
A
справедливо
V🇺
А квадрат дает за цикл больше, чем единички забирают
%M
KK
Ну смотри,
M = 3, нужно попасть в 2, изначальная точка 1, a = -1, b = 1e9
M = 3, нужно попасть в 2, изначальная точка 1, a = -1, b = 1e9
KK
Как дальше?
KK
Как вы собрались -inf набирать?
A
Но не обязательно же в y останавливаться