n villages along a road, numbered 0 to n - 1, and village i already has towers[i] cell towers. Each tower covers the villages within distance reach: a tower in village i reaches village j if |i - j| ≤ reach.
The signal of a village is the number of towers that cover it. The budget allows budget more towers with the same range; they can go into any villages, several into one if you like.
Return the largest possible value of the weakest signal among all villages once the new towers are in place.towers=[0, 3, 0, 0, 1], reach=1, budget=2 → 3
Without new towers the signals are [3, 3, 3, 1, 1]. Two new towers in village 3 give [3, 3, 5, 3, 3], a minimum of 3, and nothing does better.
towers=[2, 0, 5], reach=0, budget=4 → 3
Each tower covers only its own village. Three new towers go to village 1 and one to village 0: signals [3, 3, 5].
towers=[1, 1, 1, 1, 1, 1], reach=2, budget=0 → 3
len(towers) ≤ 10⁵towers[i] ≤ 10⁵reach ≤ n - 1budget ≤ 10⁹towers=[0, 3, 0, 0, 1], reach=1, budget=2
3
Run checks the first 3 tests in your browser. Submit checks all 121 tests on the server, hidden ones included.