size segments numbered 1 to size. Segment 1 is the entrance, and segment i continues into segments 2·i and 2·i + 1. Segments with no continuation are exits. Driving segment i costs toll[i - 1].
The cost of a route from the entrance to an exit is the sum of the tolls on all its segments, the entrance and the exit included. You may raise the toll of any segment by 1 as many times as you like, but never lower it.
What is the smallest number of raises that makes every entrance-to-exit route cost the same?size=7, toll=[2, 1, 4, 3, 5, 2, 2] → 2
The paths cost 2+1+3=6, 2+1+5=8, 2+4+2=8 and 2+4+2=8. Raising road 4 by 2 makes every path cost 8, for 2 raises in total.
size=3, toll=[9, 1, 6] → 5
The paths cost 10 and 15, so road 2 is raised by 5.
size=15, toll=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → 17
size ≤ 10⁵size + 1 is a power of twotoll) = sizetoll[i] ≤ 10⁴size=7, toll=[2, 1, 4, 3, 5, 2, 2]
2
Run checks the first 3 tests in your browser. Submit checks all 38 tests on the server, hidden ones included.