Problem:


Problem E: The Number of the Real Roots of a Cubic Equation

Description

3次方程式： が与えられるので，その正の実数根の個数，負の実数根の個数をそれぞれ調べて欲しい．

根の個数は，重根も含めて数えるものとする．

Input

入力は複数のテストケースからなり，1行目にはその個数が記される．

2行目以降はa b c dの形式で3次方程式の係数が記される．aは0ではなく，またそれぞれの数は-100から100までの整数値である．

Output

与えられた3次方程式に対し，正の実数根の個数，負の実数根の個数をスペースで区切って出力せよ．

Sample Input

2
1 3 3 1
-10 0 0 0

Output for Sample Input

0 3
0 0



Sample input:
2
1 3 3 1
-10 0 0 0


Sample output:
0 3
0 0

Submission status: Accepted

Solution code:
import math

n = int(input())

def F(a, b, c, d) :
    return lambda x : a * x**3 + b * x**2 + c * x + d
    
def X(a, b, c) :
    a = 3 * a
    b = 2 * b
    
    try :
        D = math.sqrt(b**2 - 4 * a * c)
        
        if D == 0 :
            return 0
        else :
            return (-b + D) / (2 * a), (-b - D) / (2 * a)
        
    except :
        return -1
def boa(fz, lmax, lmin, p, n) :
    if fz > 0 :
        if lmin > 0 :
            p, n = 2, 1
        else :
            n = 3
    elif fz == 0 :
        if 0 < lmin and lmax < 0 :
            p, n = 1, 1
        elif lmax > 0 :
            p = 2
        else :
            n = 2
    else :
        if lmax > 0 :
            p = 3
        else :
            p, n = 1, 2
        
    return p, n
            
def ao(fz, lmax, p, n) :
    if fz > 0 :
        n = 2
    elif fz == 0 :
        if lmax == 0 :
            p = 1
        else :
            n = 1
    else :
        if lmax > 0 :
            p = 2
        else :
            p, n = 1, 1
        
    return p, n

def bo(fz, lmin, p, n) :
    if fz > 0 :
        if lmin > 0 :
            p, n = 1, 1
        else :
            n = 2
    elif fz == 0 :
        if lmin == 0 :
            n = 1
        else :
            p = 1
    else :
        p = 2
        
    return p, n
      
def aob(fz, p, n) :
    if fz > 0 :
        n = 1
    elif fz < 0 :
        p = 1
        
    return p, n
    
def P(x, y) :
    if x > 0 :
        print(y, 0)
    elif x < 0 :
        print(0, y)
    else :
        print(0, 0)
        
for i in range(n) :
    a, b, c, d = map(int, input().split())
    if a < 0 :
        a *= -1
        b *= -1
        c *= -1
        d *= -1
        
    f = F(a, b, c, d)
    
    p = 0
    # Positive integer
    n = 0
    # Negative integer
    
    if X(a, b, c) == -1 :
        P(-d, 1)
            
    elif X(a, b, c) == 0 :
        if f(-b / (3 * a)) == 0 :
            P(-b, 3)
        else :
            P(-d, 1)
            
    else :
        if f(X(a, b, c)[0]) < f(X(a, b, c)[1]) :
            lmax = X(a, b, c)[1]
            # Local maximum
            lmin = X(a, b, c)[0]
            # Local minimum
        else :
            lmax = X(a, b, c)[0]
            lmin = X(a, b, c)[1]
        
        fmax = f(lmax)
        fmin = f(lmin)
        fz = f(0)
        
        if lmax == lmin :
            if lmax < 0 :
                print(0, 3)
            elif lmax > 0 :
                print(3, 0)
            else :
                print(0, 0)
                
        elif fmin < 0 and 0 < fmax :
            pn = boa(fz, lmax, lmin, p, n)
            print(pn[0], pn[1])
            
        elif fmax == 0 :
            pn = ao(fz, lmax, p, n)
            print(pn[0], pn[1])
            
        elif fmin == 0 :
            pn = bo(fz, lmin, p, n)
            print(pn[0], pn[1])
            
        else :
            pn = aob(fz, p, n)
            print(pn[0], pn[1])

Submission status: Accepted

Solution code:
n=int(input())
def f(a,b,c,d):
    return lambda x:a*x**3+b*x**2+c*x+d
for i in range(n):
    a,b,c,d=map(int,input().split())
    fx=f(a,b,c,d)
    D=b**2-3*a*c
    if D<=0 :
        if d==0:
            pl=mi=0
        elif (a>0 and d<0) or (a<0 and d>0):
            pl,mi=1,0
        elif (a<0 and d<0) or (a>0 and d>0):
            pl,mi=0,1
    else:
        if a>0:
            al=(-b-D**0.5)/(3*a)
            be=(-b+D**0.5)/(3*a)
            if (fx(al)<0 or fx(be)>0) and d==0:
                pl=mi=0
            elif ((fx(al)<0 or fx(be)>0) and d>0) or (fx(be)==0 and d==0 and be==0):
                pl,mi=0,1
            elif (fx(al)==0 or (fx(al)>0 and fx(be)<0)) and d==0 and be<0:
                pl,mi=0,2
            elif (fx(al)==0 or fx(be)==0 or (fx(al)>0 and fx(be)<0)) and d>0 and be<0:
                pl,mi=0,3
            elif ((fx(al)<0 or fx(be)>0) and d<0) or (fx(al)==0 and d==0 and al==0):
                pl,mi=1,0
            elif fx(al)>0 and fx(be)<0 and d==0 and al<0 and be>0:
                pl=mi=1
            elif (fx(al)==0 or (fx(al)>0 and fx(be)<0)) and d<0 and al<0:
                pl,mi=1,2
            elif (fx(be)==0 or (fx(al)>0 and fx(be)<0)) and d==0 and al>0:
                pl,mi=2,0
            elif (fx(be)==0 or (fx(al)>0 and fx(be)<0)) and d>0 and be>0:
                pl,mi=2,1
            elif ((fx(al)==0 and al>0) or fx(be)==0 or (fx(al)>0 and fx(be)<0 and al>0)) and d<0:
                pl,mi=3,0
        else:
            al=(-b+D**0.5)/(3*a)
            be=(-b-D**0.5)/(3*a)
            if (fx(al)>0 or fx(be)<0) and d==0:
                pl=mi=0
            elif ((fx(al)>0 or fx(be)<0) and d<0) or (fx(be)==0 and d==0 and be==0):
                pl,mi=0,1
            elif (fx(al)==0 or (fx(al)<0 and fx(be)>0)) and d==0 and be<0:
                pl,mi=0,2
            elif (fx(al)==0 or fx(be)==0 or (fx(al)<0 and fx(be)>0)) and d<0 and be<0:
                pl,mi=0,3
            elif ((fx(al)>0 or fx(be)<0) and d>0) or (fx(al)==0 and d==0 and al==0):
                pl,mi=1,0
            elif fx(al)<0 and fx(be)>0 and d==0 and al<0 and be>0:
                pl=mi=1
            elif (fx(al)==0 or (fx(al)<0 and fx(be)>0)) and d>0 and al<0:
                pl,mi=1,2
            elif (fx(be)==0 or (fx(al)<0 and fx(be)>0)) and d==0 and al>0:
                pl,mi=2,0
            elif (fx(be)==0 or (fx(al)<0 and fx(be)>0)) and d<0 and be>0:
                pl,mi=2,1
            elif (fx(al)==0 or fx(be)==0 or (fx(al)<0 and fx(be)>0)) and d>0 and al>0:
                pl,mi=3,0
    print(pl,mi)

Submission status: Accepted

Solution code:
import math

def make_func1(a, b, c, d):
    return lambda X : a*X**3 + b*X**2 + c*X + d
def make_func2(a, b, c):
    return lambda x : 3*a*x**2 + 2*b*x + c

i = int(input())
for j in range(i):
    a, b, c, d = map(int, input().split())
    fX = make_func1(a, b, c, d)
    fx = make_func2(a, b, c)
    D_4 = b**2 - 3*a*c
    
    if D_4<=0:
        if 0<a:
            if d<0:
                pos=1
                neg=0
            if d==0:
                pos=0
                neg=0
            if 0<d:
                pos=0
                neg=1
        if a<0:
            if d<0:
                pos=0
                neg=1
            if d==0:
                pos=0
                neg=0
            if 0<d:
                pos=1
                neg=0
    
    if D_4>0 :
        if 0<a:
            p = (-b-math.sqrt(b**2-3*a*c))/(3*a)
            q = (-b+math.sqrt(b**2-3*a*c))/(3*a)
            if 0<fX(q) or fX(p)<0 :
                if d<0:
                    pos=1
                    neg=0
                if d==0:
                    pos=0
                    neg=0
                if 0<d:
                    pos=0
                    neg=1
            if fX(q)==0:
                if d<0:
                    pos=3
                    neg=0
                if d==0 and 0<p:
                    pos=2
                    neg=0
                if 0<d and 0<q:
                    pos=2
                    neg=1
                if d==0 and q==0:
                    pos=0
                    neg=1
                if 0<d and q<0:
                    pos=0
                    neg=3
            if fX(p)==0:
                if d<0 and 0<p:
                    pos=3
                    neg=0
                if d==0 and p==0:
                    pos=1
                    neg=0
                if d<0 and p<0:
                    pos=1
                    neg=2
                if d==0 and q<0:
                    pos=0
                    neg=2
                if 0<d and q<0:
                    pos=0
                    neg=3
            if fX(q)<0<fX(p):
                if d<0 and 0<p:
                    pos=3
                    neg=0
                if d==0 and 0<p:
                    pos=2
                    neg=0
                if 0<d and 0<q:
                    pos=2
                    neg=1
                if d==0 and p<0<q:
                    pos=1
                    neg=1
                if d<0 and p<0:
                    pos=1
                    neg=2
                if d==0 and q<0:
                    pos=0
                    neg=2
                if 0<d and q<0:
                    pos=0
                    neg=3
        
        if a<0:
            p = (-b+math.sqrt(b**2-3*a*c))/(3*a)
            q = (-b-math.sqrt(b**2-3*a*c))/(3*a)
            if 0<fX(p) or fX(q)<0 :
                if d<0:
                    pos=0
                    neg=1
                if d==0:
                    pos=0
                    neg=0
                if 0<d:
                    pos=1
                    neg=0
            if fX(p)==0:
                if 0<d and 0<p:
                    pos=3
                    neg=0
                if d==0 and p==0:
                    pos=1
                    neg=0
                if 0<d and p<0:
                    pos=1
                    neg=2
                if d==0 and q<0:
                    pos=0
                    neg=2
                if d<0 and q<0:
                    pos=0
                    neg=3
            if fX(q)==0:
                if 0<d and 0<p:
                    pos=3
                    neg=0
                if d==0 and 0<p:
                    pos=2
                    neg=0
                if d<0 and 0<q:
                    pos=2
                    neg=1
                if d==0 and q==0:
                    pos=0
                    neg=1
                if d<0 and q<0:
                    pos=0
                    neg=3
            if fX(p)<0<fX(q):
                if 0<d and 0<p:
                    pos=3
                    neg=0
                if d==0 and 0<p:
                    pos=2
                    neg=0
                if d<0 and 0<q:
                    pos=2
                    neg=1
                if d==0 and p<0<q:
                    pos=1
                    neg=1
                if 0<d and p<0:
                    pos=1
                    neg=2
                if d==0 and q<0:
                    pos=0
                    neg=2
                if d<0 and q<0:
                    pos=0
                    neg=3
    
    print(pos,neg)

Submission status: Accepted

Solution code:
import math

n = int(input())

def F(a, b, c, d) :
    return lambda x : a * x**3 + b * x**2 + c * x + d
    
def X(a, b, c) :
    a = 3 * a
    b = 2 * b
    
    try :
        D = math.sqrt(b**2 - 4 * a * c)
        
        if D == 0 :
            return 0
        else :
            return (-b + D) / (2 * a), (-b - D) / (2 * a)
        
    except :
        return -1
    
def boa(fz, lmax, lmin, p, n) :
    if fz > 0 :
        if lmin > 0 :
            p, n = 2, 1
        else :
            n = 3
    elif fz == 0 :
        if 0 < lmin and lmax < 0 :
            p, n = 1, 1
        elif lmax > 0 :
            p = 2
        else :
            n = 2
    else :
        if lmax > 0 :
            p = 3
        else :
            p, n = 1, 2
        
    return p, n
            
def ao(fz, lmax, p, n) :
    if fz > 0 :
        n = 2
    elif fz == 0 :
        if lmax == 0 :
            p = 1
        else :
            n = 1
    else :
        if lmax > 0 :
            p = 2
        else :
            p, n = 1, 1
        
    return p, n

def bo(fz, lmin, p, n) :
    if fz > 0 :
        if lmin > 0 :
            p, n = 1, 1
        else :
            n = 2
    elif fz == 0 :
        if lmin == 0 :
            n = 1
        else :
            p = 1
    else :
        p = 2
        
    return p, n
      
def aob(fz, p, n) :
    if fz > 0 :
        n = 1
    elif fz < 0 :
        p = 1
        
    return p, n
    
def P(x, y) :
    if x > 0 :
        print(y, 0)
    elif x < 0 :
        print(0, y)
    else :
        print(0, 0)
        
for i in range(n) :
    a, b, c, d = map(int, input().split())
    if a < 0 :
        a *= -1
        b *= -1
        c *= -1
        d *= -1
        
    f = F(a, b, c, d)
    
    p = 0
    # Positive integer
    n = 0
    # Negative integer
    
    if X(a, b, c) == -1 :
        P(-d, 1)
            
    elif X(a, b, c) == 0 :
        if f(-b / (3 * a)) == 0 :
            P(-b, 3)
        else :
            P(-d, 1)
            
    else :
        if f(X(a, b, c)[0]) < f(X(a, b, c)[1]) :
            lmax = X(a, b, c)[1]
            # Local maximum
            lmin = X(a, b, c)[0]
            # Local minimum
        else :
            lmax = X(a, b, c)[0]
            lmin = X(a, b, c)[1]
        
        fmax = f(lmax)
        fmin = f(lmin)
        fz = f(0)
        
        if lmax == lmin :
            if lmax < 0 :
                print(0, 3)
            elif lmax > 0 :
                print(3, 0)
            else :
                print(0, 0)
                
        elif fmin < 0 and 0 < fmax :
            pn = boa(fz, lmax, lmin, p, n)
            print(pn[0], pn[1])
            
        elif fmax == 0 :
            pn = ao(fz, lmax, p, n)
            print(pn[0], pn[1])
            
        elif fmin == 0 :
            pn = bo(fz, lmin, p, n)
            print(pn[0], pn[1])
            
        else :
            pn = aob(fz, p, n)
            print(pn[0], pn[1])

Submission status: Accepted

Solution code:
import sys,queue,math,copy
from fractions import gcd
input = sys.stdin.readline
INF = 10**4
EPS = 10 ** (-8)
LI = lambda : [int(x) for x in input().split()]
_LI = lambda : [int(x)-1 for x in input().split()]

N = int(input())
for _ in range(N):

    a,b,c,d = LI()
    if a < 0:
        a = -a
        b = -b
        c = -c
        d = -d
    f = lambda x: a*x*x*x + b*x*x + c*x + d

    a_plus = 0
    a_minus = 0
    D = b * b - 3 * a * c

    def count(x, y):
        global a_plus,a_minus
        if x > 0:
            a_plus += y
        elif x < 0:
            a_minus += y

    if D < 0:
        # 単調増加/減少
        count(-d,1)
    elif D == 0:
        if f(-b/(3*a)) == 0: #３重解
            count(-b,3)
        else: # 単調増加
            count(-d,1)
    else:
        x1 = (- b - math.sqrt(D)) / (3*a)
        x2 = (- b + math.sqrt(D)) / (3*a)

        def bs(h,l):
            if min(h,l) <= 0 <= max(h,l)  and f(0) == 0:
                return 0
            while f(h) > f(l) + EPS:
                m = (h + l)/2
                if f(m) > 0:
                    h = m
                else:
                    l = m
            return l

        if f(x1) > 0:
            a1 = bs(x1,-INF)
            count(a1,1)
            if f(x2) < 0:
                a1 = bs(x1,x2)
                count(a1,1)
                a1 = bs(INF,x2)
                count(a1,1)

            elif f(x2) == 0:
                count(x2,2)
        elif f(x1) == 0:
            count(x1,2)
            a1 = bs(INF,x2)
            count(a1,1)
        else: #f(x1) < 0
            a1 = bs(INF,x2)
            count(a1,1)

    print (a_plus, a_minus)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
EPS = 10 ** -8

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索(小数用) """

    ok = mn
    ng = mx
    while abs(ok-ng) > 10**-12:
        mid = (ok+ng) / 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

# 2次方程式の解の公式
def dim2formula(a, b, c):
    from math import sqrt

    try:
        return (-b+sqrt(pow(b, 2)-4*a*c))/(2*a), (-b-sqrt(pow(b, 2)-4*a*c))/(2*a)
    # 解なしはNoneを返却
    except ValueError:
        return (None, None)

# 3次→2次への微分
def calc1(a, b, c, d):
    a *= 3
    b *= 2
    return (a, b, c)

# ax^3+bx^2+cx+dを解く
def calc2(x):
    return a*x**3 + b*x**2 + c*x + d

# /のグラフ用
def check1(x):
    res = calc2(x)
    return res < 0

# \のグラフ用
def check2(x):
    res = calc2(x)
    return res > 0

for _ in range(INT()):
    a, b, c, d = MAP()
    ans = [0] * 2

    a2, b2, c2 = calc1(a, b, c, d)
    ans1, ans2 = dim2formula(a2, b2, c2)

    # 微分して解いた結果が解なしなら、元の式は極値なしで解は1つ
    if ans1 is None:
        if a > 0:
            # /のグラフ
            x = bisearch_max(-INF, INF, check1)
        else:
            # \のグラフ
            x = bisearch_max(-INF, INF, check2)
        # x = 0 ならカウントしない
        if abs(x) < EPS:
            pass
        elif x > 0:
            ans[0] += 1
        elif x < 0:
            ans[1] += 1
    # それ以外なら解は重解も含めると解は3つ
    else:
        ans1, ans2 = min(ans1, ans2), max(ans1, ans2)
        # /\/のグラフ
        if a > 0:
            res1 = bisearch_max(-INF, ans1, check1)
            res2 = bisearch_max(ans1, ans2, check2)
            res3 = bisearch_max(ans2, INF, check1)
        # \/\のグラフ
        else:
            res1 = bisearch_max(-INF, ans1, check2)
            res2 = bisearch_max(ans1, ans2, check1)
            res3 = bisearch_max(ans2, INF, check2)

        # 3つの解候補
        for x in [res1, res2, res3]:
            # f(x) = 0 について確認
            if abs(calc2(x)) < EPS:
                # x = 0 ならカウントしない
                if abs(x) < EPS:
                    continue
                elif x > 0:
                    ans[0] += 1
                elif x < 0:
                    ans[1] += 1
    print(*ans)

Submission status: Runtime Error

Solution code:
import math

w1 = 1
w2 = 1/2 * (-1 + math.sqrt(3)*1j)
w3 = 1/2 * (-1 - math.sqrt(3)*1j)

n = int(input())
for i in range(n):
  aa, bb, cc, dd = map(int, input().split())
  a = bb / aa
  b = cc / aa
  c = dd / aa
  p = -1/54 * (27 * c + 2 * (a ** 3) - 9 * a * b)
  q = 1/9 * (3 * b - a ** 2)
  r = 1/3 * a
  
  x1 = w1 * (p + math.sqrt(p ** 2 + q ** 3)) ** (1/3) + w1 * (p - math.sqrt(p ** 2 + q ** 3)) ** (1/3) - r
  x2 = w2 * (p + math.sqrt(p ** 2 + q ** 3)) ** (1/3) + w3 * (p - math.sqrt(p ** 2 + q ** 3)) ** (1/3) - r
  x3 = w3 * (p + math.sqrt(p ** 2 + q ** 3)) ** (1/3) + w2 * (p - math.sqrt(p ** 2 + q ** 3)) ** (1/3) - r
  
  plus = 0
  minus = 0
  
  for i in [x1, x2, x3]:
    if i.imag == 0:
      i = i.real
      if i > 0:
        plus += 1
      elif i < 0:
        minus += 1
  print(plus, minus)