글 읽기 - 시간 초과...

jun2077681 5년 전 0

여기서 더 어떻게 최적화를 해야하는지 도저히 감이 안잡힙니다...ㅠㅠ

import sys
from fractions import gcd

class fraction:
    def __init__(self, numerator, denominator):
        self.numerator = abs(numerator)
        #--------------------
        self.denominator = abs(denominator)
        self.sign = (numerator * denominator >= 0)

    def toTuple(self):
        if self.sign:
            return (self.numerator, self.denominator)
        else:
            return (self.numerator * -1, self.denominator)

def minus(a1, a2):
    nu1 = a1.numerator
    nu2 = a2.numerator

    if a1.sign == False:
        nu1 *= -1
    if a2.sign == False:
        nu2 *= -1

    deno = a1.denominator * a2.denominator
    nu = nu1 * a2.denominator - a1.denominator * nu2
    g = gcd(deno, abs(nu))

    return fraction(nu//g, deno//g)

def isFinish(a1):
    return a1.numerator == 1 and a1.denominator < 1000000

s = map(lambda x: map(int, x.split()), sys.stdin.readlines())

for i in s:
    a,b = i
    if a == 0 and b == 0: break
    x = fraction(a, b)
    l = []

    while True:
        a, b = x.toTuple()
        x1 = 0
        if b % a == 0:
            x1 = b//a
        else:
            x1 = b//a + 1

        while True:
            r = minus(x, fraction(1, x1))
            if r.denominator < 1000000:
                break
            x1 += 1
        
        l.append(str(x1))
        x = r
        if isFinish(x):
            l.append(str(x.denominator))
            break
    print(' '.join(l))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과...

jun2077681 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말