글 읽기 - TC 모두 통과하는 것 같은데 뭐가 문제인지 모르겠습니다..

lycoris1600 2년 전 0

15682번 예제와 9735번 문제의 게시판에 있는 모든 TC를 전부 통과하는데 왜 계속 틀렸습니다가 나오는지 모르겠습니다..

미분해서 근을 구한 후, 3중근이 나오는 부분만 예외처리하고, 2중근의 경우는 근 하나와 나머지 범위 하나에서 이분탐색, 중근이 없는 경우는 이분탐색을 하는 알고리즘으로 구성했습니다.

혹시 반례가 있을까요?

9735번에 이 코드를 제출해보니 통과합니다

from decimal import*
getcontext().prec=100
for i in range(int(input())):
    A,B,C,d=map(D:=Decimal,input().split())
    def f(x):
        return A*x**3+B*x**2+C*x+d
    def find(s,e):
        while e-s>10**-10:
            p=(s+e)/2
            if f(p)*f(s)>0:
                s=p
            else:
                e=p
        return s
    if B**2-3*A*C<0:
        ans=[find(D(-1000000),D(1000000))]
    else:
        sol=sorted([(-B-(B**2-3*A*C)**D('0.5'))/(3*A),(-B+(B**2-3*A*C)**D('0.5'))/(3*A)])
        if round(f(sol[0])*f(sol[1]),11)>0:
            ans=[find(D(-1000000),D(1000000))]
        elif round(f(sol[0]),11)==0 or round(f(sol[1]),11)==0:
            if round(f(sol[0]),11)==0:
                if round(sol[0],11)==round(sol[1],11):
                    ans=[sol[0]]
                else:
                    ans=[sol[0],find(sol[1],D(1000000))]
            else:
                ans=[find(D(-1000000),sol[0]),sol[1]]
        else:
            ans=[find(D(-1000000),sol[0]),find(sol[0],sol[1]),find(sol[1],D(1000000))]
    ans=['{:.10f}'.format(i) for i in ans]
    print(*ans)