Submission #66350425

Source Code Expand

from sympy import Rational, continued_fraction, continued_fraction_reduce
from math import gcd

T = int(input())

for i in range(T):
    A, B, C, D = map(int, input().split(' '))
    g1 = gcd(A, B)
    g2 = gcd(C, D)
    a = A // g1
    b = B // g1
    c = C // g2
    d = D // g2
    if b * c - a * d == 1:
        print(b + d)
        continue
    
    r1 = Rational(A, B)
    r2 = Rational(C, D)
    cf1 = continued_fraction(r1)
    cf2 = continued_fraction(r2)
    k = 0
    l = min(len(cf1), len(cf2))
    while k < l and cf1[k] == cf2[k]:
        k += 1

    if k < l:
        x = min(cf1[k], cf2[k])
    else:
        if k < len(cf1):
            x = cf1[k]
        else:
            x = cf2[k]
    
    ncf = cf1[:k] + [x + 1]
    ans = continued_fraction_reduce(ncf)
    if r1 < ans and ans < r2:
        print(ans.as_numer_denom()[1])
        continue
    
    while True:
        ncf.append(1)
        ans = continued_fraction_reduce(ncf)
        if r1 < ans and ans < r2:
            print(ans.as_numer_denom()[1])
            break

Submission Info

Submission Time
Task G - A/B < p/q < C/D
User lX57
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 1089 Byte
Status TLE
Exec Time 2221 ms
Memory 228824 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 625
Status
AC × 1
AC × 8
TLE × 27
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 01_handmade_07.txt, 01_handmade_08.txt, 01_handmade_09.txt, 01_handmade_10.txt, 01_handmade_11.txt, 01_handmade_12.txt, 01_handmade_13.txt, 01_handmade_14.txt, 01_handmade_15.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1096 ms 160548 KiB
01_handmade_00.txt TLE 2216 ms 176268 KiB
01_handmade_01.txt TLE 2216 ms 187132 KiB
01_handmade_02.txt AC 1530 ms 163060 KiB
01_handmade_03.txt TLE 2221 ms 214736 KiB
01_handmade_04.txt TLE 2217 ms 202016 KiB
01_handmade_05.txt TLE 2216 ms 186404 KiB
01_handmade_06.txt AC 1497 ms 161632 KiB
01_handmade_07.txt TLE 2218 ms 224920 KiB
01_handmade_08.txt TLE 2218 ms 223680 KiB
01_handmade_09.txt AC 1501 ms 163176 KiB
01_handmade_10.txt AC 1477 ms 162776 KiB
01_handmade_11.txt AC 1493 ms 163756 KiB
01_handmade_12.txt AC 1482 ms 161748 KiB
01_handmade_13.txt AC 1506 ms 162568 KiB
01_handmade_14.txt TLE 2218 ms 206596 KiB
01_handmade_15.txt TLE 2217 ms 203996 KiB
02_random_00.txt TLE 2218 ms 221068 KiB
02_random_01.txt TLE 2221 ms 221384 KiB
02_random_02.txt TLE 2218 ms 223492 KiB
02_random_03.txt TLE 2218 ms 216372 KiB
02_random_04.txt TLE 2219 ms 228824 KiB
02_random_05.txt TLE 2218 ms 216132 KiB
02_random_06.txt TLE 2218 ms 219448 KiB
02_random_07.txt TLE 2220 ms 215676 KiB
02_random_08.txt TLE 2218 ms 213104 KiB
02_random_09.txt TLE 2218 ms 212620 KiB
02_random_10.txt TLE 2218 ms 213624 KiB
02_random_11.txt TLE 2219 ms 223612 KiB
02_random_12.txt TLE 2221 ms 213256 KiB
02_random_13.txt TLE 2218 ms 215004 KiB
02_random_14.txt TLE 2218 ms 216660 KiB
02_random_15.txt TLE 2218 ms 216856 KiB
02_random_16.txt TLE 2218 ms 211440 KiB
02_random_17.txt TLE 2218 ms 210048 KiB