size участков, пронумерованных от 1 до size. Участок 1 — въезд, у участка i два продолжения: 2·i и 2·i + 1. Участки без продолжений — выезды. Проезд по участку i стоит toll[i - 1].
Стоимость маршрута от въезда до выезда — сумма плат на всех его участках, включая въезд и выезд. Плату на любом участке можно повышать на 1 сколько угодно раз, понижать нельзя.
Какое наименьшее число повышений нужно, чтобы все маршруты от въезда до выездов стоили одинаково?size=7, toll=[2, 1, 4, 3, 5, 2, 2] → 2
Пути до развязок: 2+1+3=6, 2+1+5=8, 2+4+2=8, 2+4+2=8. Поднимаем плату на дороге 4 на 2 — все пути стоят 8, всего 2 повышения.
size=3, toll=[9, 1, 6] → 5
Пути стоят 10 и 15 — поднимаем дорогу 2 на 5.
size=15, toll=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → 17
size ≤ 10⁵size + 1 — степень двойкиtoll) = sizetoll[i] ≤ 10⁴size=7, toll=[2, 1, 4, 3, 5, 2, 2]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 38 тестов на сервере, включая скрытые.