zogzog

Untitled

Jun 22nd, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.25 KB | None | 0 0
  1. #!/usr/bin/env python3
  2. import sys
  3.  
  4. MAX_B = 20
  5. MAX_S = 1000000
  6. MAX_F = 20
  7. MAX_E = 1000000
  8. MAX_M = 1000000
  9.  
  10. INF = MAX_E * 222222
  11.  
  12. def binary_search(key, F):
  13.   """Binary search in F over the range [0, INF] looking for 'key'."""
  14.   lo = 0
  15.   hi = INF
  16.   for it in range(200):
  17.     mid = lo/2.0 + hi/2.0
  18.     print(mid)
  19.     if F(mid) < key:
  20.       lo = mid
  21.     else:
  22.       hi = mid
  23.   return mid
  24.  
  25.  
  26. def main():
  27.   B = int(input())
  28.   assert 1 <= B <= MAX_B
  29.   bands = [tuple(map(float, input().split())) for _ in range(B)]
  30.   assert all(0 < s <= MAX_S for s, _ in bands)
  31.   assert all(0 <= p <= 100 for _, p in bands)
  32.   P = float(input())
  33.   assert 0 <= P <= 100
  34.   bands.append((INF, P))
  35.   F = int(input())
  36.   assert 0 < F <= MAX_F
  37.  
  38.   def get_taxes(money):
  39.     """Returns the taxes that should be paid with 'money' income."""
  40.     t = 0
  41.     for s, p in bands:
  42.       b = min(money, s)
  43.       t += (b * p)/100
  44.       money -= s
  45.       if money < 0:
  46.         break
  47.     return t
  48.  
  49.   for _ in range(F):
  50.     e, m = map(float, input().split())
  51.     assert 0 <= e <= MAX_E
  52.     assert 0 <= m <= MAX_M
  53.     taxes_e = get_taxes(e)
  54.     result = binary_search(m, lambda k : k - get_taxes(e + k) + taxes_e)
  55.     print(result)
  56.  
  57.  
  58. if __name__ == '__main__':
  59.   main()
Advertisement
Add Comment
Please, Sign In to add comment