Roller coaster

import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate, groupby
from functools import lru_cache, cmp_to_key, reduce
from math import gcd, isqrt, comb, inf, pi, sqrt, atan2, hypot, ceil
from fractions import Fraction

def main():
    data = sys.stdin.buffer.read().split(); idx = 0
    n = int(data[idx]); idx += 1
    # n, m = map(int, data[idx:idx + 2]); idx += 2
    # a = list(map(int, data[idx:idx + n])); idx += n
    # s = data[idx].decode(); idx += 1                  # strings

    P = []
    R = []
    A = []
    F = []

    for _ in range(n):
        a, b, c, d = map(int, data[idx:idx + 4]); idx += 4
        P.append(a)
        R.append(b)
        A.append(c)
        F.append(d)

    # g = [data[idx + i].decode() for i in range(n)]; idx += n  # grid of n rows, no spaces, strings

    # input = sys.stdin.readline
    # n, m = map(int, input().split())
    # s = input().strip()  # strip removes the trailing newline
    # for line in sys.stdin:  # read until EOF

    # out = []

    # def fn(s):
    #     not_happy = 0
    #     for i in range(n):
    #         if s < R[i]: 
    #             return 0
    #             return i
    #         if s < P[i]: 
    #             not_happy += 1
    #         s = s*(1-F[i]/100) - A[i]

    #     # if s < 0:
    #     #     return 0

    #     if not_happy >= (n+1) // 2:
    #         # return 50 + not_happy 
    #         return 0


    #     return 100

    # # l = list(range(10000000))
    # # idx = bisect_left(l, 99, key=fn)
    # # print(idx)


    # def bl(f, target, lo, hi):
    #     while lo < hi:
    #         mid = lo + (hi - lo) // 2
    #         if f(mid) < target:
    #             lo = mid + 1
    #         else:
    #             hi = mid
    #     return lo

    
    # print(bl(fn, 99, 0, 10**100))

    # for i in range(2010101010100993900150785-1, 2010101010100993900150785 +2):
    #     print(i, fn(i))
    
    
    # print("not found")
    # return -1


    happy_when_more_than = []
    min_speed = R[n-1]
    for i in range(n-1, -1, -1):

        if i == n-1:
            min_speed = R[n-1]
        else:
            # min_speed = (min_speed + A[i]) / (1-F[i]/100)
            min_speed = (min_speed + A[i]) * Fraction(100, 100 - F[i])
            min_speed = max(min_speed, R[i])


        for j in range(len(happy_when_more_than)):
            # happy_when_more_than[j] = (happy_when_more_than[j] + A[i]) / (1-F[i]/100)
            happy_when_more_than[j] = (happy_when_more_than[j] + A[i]) * Fraction(100, 100 - F[i])

        happy_when_more_than.append(P[i])
        # print(i, happy_when_more_than)


        # if s < R[i]: 
        #     return 0
        #     return i
        # if s < P[i]: 
        #     not_happy += 1
        # s = s*(1-F[i]/100) - A[i]

    happy_when_more_than.sort()
    # print(happy_when_more_than)
    # print(min_speed)

    out = ceil(max(happy_when_more_than[(n+1)//2 - 1], min_speed))
    print(out)


    # sys.stdout.write("\n".join(map(str, out)) + "\n")  # one value per line
    # print(*out)                                      # space separated on one line
    # print(f"{ans:.6f}")                              # float with 6 decimals
    # print("\n".join("".join(row) for row in g))      # grid of chars


main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED