CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Roller coaster
Sender:aalto2024i_006
Submission time:2024-10-30 17:37:20 +0200
Language:Python3 (PyPy3)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.08 sdetails
#2ACCEPTED0.16 sdetails
#3ACCEPTED0.09 sdetails
#4ACCEPTED0.09 sdetails
#5ACCEPTED0.08 sdetails
#6ACCEPTED0.09 sdetails
#7ACCEPTED0.09 sdetails
#8ACCEPTED0.11 sdetails
#9ACCEPTED0.12 sdetails
#10ACCEPTED0.09 sdetails
#11ACCEPTED0.09 sdetails
#12ACCEPTED0.09 sdetails

Code

import sys
from fractions import Fraction

input = sys.stdin.readline

n = int(input())
p = [0] * n
r = [0] * n
a = [0] * n
f = [0] * n

for i in range(n):
    p[i], r[i], a[i], f[i] = map(int, input().split())

def check(speed):
    x = Fraction(speed)
    cnt = n
    for i in range(n):
        if x < r[i]:
            return False
        if x < p[i]:
            cnt -= 1
        x = x - a[i] - Fraction(x * f[i], 100)
    return cnt >= (n + 1) // 2

low = 0
high = 1
while not check(high):
    high *= 2

ans = -1
while low <= high:
    mid = (low + high) // 2
    if check(mid):
        ans = mid
        high = mid - 1
    else:
        low = mid + 1

print(ans)

Test details

Test 1

Verdict: ACCEPTED

input
3
1000 5 5 0
20 20 20 50
50 50 0 99

correct output
145

user output
145

Test 2

Verdict: ACCEPTED

input
10
1000000 1000000 1000000 99
1000000 1000000 1000000 99
1000000 1000000 1000000 99
1000000 1000000 1000000 99
...

correct output
2010101010101010100000000

user output
2010101010101010100000000

Test 3

Verdict: ACCEPTED

input
7
794772 933488 441001 5
271493 536110 509532 51
962838 821872 870163 38
499748 375441 611720 27
...

correct output
19316405

user output
19316405

Test 4

Verdict: ACCEPTED

input
3
596853 888598 841235 97
66172 267459 123646 63
797926 471325 495185 83

correct output
81642158

user output
81642158

Test 5

Verdict: ACCEPTED

input
1
96033 88994 378596 21

correct output
96033

user output
96033

Test 6

Verdict: ACCEPTED

input
4
621429 570665 136758 47
960437 633256 497081 80
609067 68711 635017 1
952965 878149 492025 33

correct output
19366822

user output
19366822

Test 7

Verdict: ACCEPTED

input
4
318031 108177 756250 50
502140 162500 94476 8
20779 421098 576089 37
839335 802331 61705 28

correct output
6474336

user output
6474336

Test 8

Verdict: ACCEPTED

input
10
267853 777820 375951 88
988230 882388 775839 83
967127 555787 30414 59
813651 989181 261150 83
...

correct output
114240784216

user output
114240784216

Test 9

Verdict: ACCEPTED

input
10
861881 84483 508595 97
274330 38611 473 18
695015 614973 493097 97
770531 391287 334900 98
...

correct output
26667465547194

user output
26667465547194

Test 10

Verdict: ACCEPTED

input
6
993908 158176 414002 83
50631 75954 861168 68
98702 383452 611097 7
953893 532084 225127 4
...

correct output
46921821

user output
46921821

Test 11

Verdict: ACCEPTED

input
4
388404 393603 132467 24
739054 45905 89323 17
259460 850672 530957 26
420175 673047 31765 58

correct output
2895218

user output
2895218

Test 12

Verdict: ACCEPTED

input
8
643002 391445 280110 17
195187 908655 709512 0
354760 527205 486247 77
84740 350249 581194 78
...

correct output
250399569

user output
250399569