budget cuts

 1"""
 2time: O(log b * |G|)
 3space: O(1)
 4"""
 5
 6def find_grants_cap(G, b):
 7  comp_total = lambda c: sum(min(c, g) for g in G)
 8  l, r = 0, b
 9  while l < r:
10    m = (l + r) / 2
11    total = comp_total(m)
12    if abs(total - b) < 0.0001:
13      return m
14    else:
15      l, r = ((m, r),(l, m))[total > b]
16
17print(find_grants_cap([2, 100, 50, 120, 1000], 190))