Problem:


Problem C: Factorization

Problem

ukuku1333さんはおっちょこちょいなので、
x の一次式の積を展開したら、元の一次式がわからなくなってしまった。

x の n 次多項式が与えられるので、因数分解して元のxの一次式の積の形にせよ。

x の n 次多項式は以下のBNFによって与えられる。

<多項式> &#058;&#061; <項> &#124; <多項式>&plus;<項> &#124; <多項式>&minus;<項> 
<項> &#058;&#061; x&#094;<指数> &#124; <係数>x&#094;<指数> &#124; <係数>x &#124; <定数> 
<指数> &#058;&#061; &#091;2-5&#093; 
<係数> &#058;&#061; &#091;1-9&#093;&#091;0-9&#093;&#042; 
<定数> &#058;&#061; &#091;1-9&#093;&#091;0-9&#093;&#042; 

指数及び係数が省略されている場合は1とみなす。

Input

入力は以下の形式で与えられる。

S

x の n 次多項式を表す文字列 S が一行に与えられる。

Constraints

入力は以下の条件を満たす。

    
2 ≤ n ≤ 5

    
与えられる式の項の数を m とすると、1 ≤ i < j ≤ m  なる任意の i, j  の組に対して、

        i 番目の項の次数は j 番目の項の次数より大きいことが保証される
    

    
与えられるx の n 次多項式は、x の一次式の積の形に因数分解したもので表すことができることが保証される

    
係数、定数の絶対値はそれぞれ2&times;103以下である

    
次数が最大のものの係数は1であり、省略されていることが保証される

    
展開する前のそれぞれの一次式の元の定数項は0ではない整数であることが保証される

    
展開する前のそれぞれの一次式の元の定数項は相異なることが保証される

    

Output

S をx の一次式の積の形に因数分解したものを、定数項の小さいものから順に出力せよ。

出力の最後には改行を入れること。

Sample Input 1

x^2+3x+2

Sample Output 1

(x+1)(x+2)

Sample Input 2

x^2-1

Sample Output 2

(x-1)(x+1)

Sample Input 3

x^5+15x^4+85x^3+225x^2+274x+120

Sample Output 3

(x+1)(x+2)(x+3)(x+4)(x+5)

Sample Input 4

x^3-81x^2-1882x-1800

Sample Output 4

(x-100)(x+1)(x+18)



Sample input:
x^2+3x+2


Sample output:
(x+1)(x+2)

Submission status: Wrong Answer

Solution code:
import copy
s = input()
k = [0] * 6
t = []
while True:
    i = 0
    if "+" in s[1:]:
        i = 1 + s[1:].index("+")
    if "-" in s[1:]:
        if i > 0:i = min(i, 1 + s[1:].index("-"))
        else:i = 1 + s[1:].index("-")
    if i == 0:
        k[0] = int(s)
        break
    j = s.index("x")
    if j + 3 == i:
        if j == 0:k[int(s[j + 2])] = 1
        else:k[int(s[j + 2])] = int(s[:j])
    else:
        if j == 0:k[1] = 1
        else:k[1] = int(s[:j])
    s = s[i:]
while True:
    if k[-1] == 0:k.pop()
    else:break
while True:
    i = 1
    while i <= abs(k[0]):
        if k[0] % i == 0:
            j = k[0] // i
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
            j *= -1
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
        i += 1
    if len(k) == 2:
        t.append(k[1])
        break
t.sort()
s = ""
for i in t:s += "(x{})".format(i) if i < 0 else "(x+{})".format(i)
print(s)

Submission status: Wrong Answer

Solution code:
import copy
s = input()
k = [0] * 6
t = []
while True:
    i = 0
    if "+" in s[1:]:
        i = 1 + s[1:].index("+")
    if "-" in s[1:]:
        if i > 0:i = min(i, 1 + s[1:].index("-"))
        else:i = 1 + s[1:].index("-")
    if i == 0:
        k[0] = int(s)
        break
    j = s.index("x")
    if j + 3 == i:
        if j == 0:k[int(s[j + 2])] = 1
        else:k[int(s[j + 2])] = int(s[:j])
    else:
        if j == 0:k[1] = 1
        elif j == 1:k[1] = -1
        else:k[1] = int(s[:j])
    s = s[i:]
while True:
    if k[-1] == 0:k.pop()
    else:break
while True:
    i = 1
    while i <= abs(k[0]):
        if k[0] % i == 0:
            j = k[0] // i
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
            j *= -1
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
        i += 1
    if len(k) == 2:
        print(k)
        t.append(k[0])
        break
t.sort()
s = ""
for i in t:s += "(x{})".format(i) if i < 0 else "(x+{})".format(i)
print(s)

Submission status: Wrong Answer

Solution code:
import copy
s = input()
k = [0] * 6
t = []
while True:
    i = 0
    if "+" in s[1:]:
        i = 1 + s[1:].index("+")
    if "-" in s[1:]:
        if i > 0:i = min(i, 1 + s[1:].index("-"))
        else:i = 1 + s[1:].index("-")
    if i == 0:
        k[0] = int(s)
        break
    j = s.index("x")
    if j + 3 == i:
        if j == 0:k[int(s[j + 2])] = 1
        else:k[int(s[j + 2])] = int(s[:j])
    else:
        if j == 0:k[1] = 1
        elif j == 1:k[1] = -1
        else:k[1] = int(s[:j])
    s = s[i:]
while True:
    if k[-1] == 0:k.pop()
    else:break
while True:
    i = 1
    while i <= abs(k[0]):
        if k[0] % i == 0:
            j = k[0] // i
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
            j *= -1
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
        i += 1
    if len(k) == 2:
        t.append(k[0])
        break
t.sort()
s = ""
for i in t:s += "(x{})".format(i) if i < 0 else "(x+{})".format(i)
print(s)

Submission status: Accepted

Solution code:
S = input()
L = len(S)

cur = 0
P = [0]*6
def expr():
    global cur
    op = "+"
    while 1:
        term(op)
        if cur == L:
            break
        op = S[cur]
        cur += 1 # "+"/"-"

def num():
    global cur
    v = 0
    while cur < L and S[cur] in "0123456789":
        v = 10*v + int(S[cur])
        cur += 1
    return v

def term(op):
    global cur
    k = 1
    if S[cur] != 'x':
        k = num()
    d = 0
    if cur < L and S[cur] == "x":
        cur += 1 # "x"
        d = 1
        if cur < L and S[cur] == '^':
            cur += 1 # "^"
            d = num()
    P[d] = k if op == '+' else -k
expr()

def f(P, x):
    res = 0
    for i in range(6):
        res += P[i]*(x**i)
    return res

d = 5
while P[d] == 0:
    d -= 1

R = []
for x in range(2000, -2001, -1):
    if f(P, x) == 0:
        R.append(x)

print("".join("(x%+d)" % -x for x in R))

Submission status: Accepted

Solution code:
def parse(S):
    poly = []
    t = []
    for x in S.split('+'):
        if '-' in x:
            t = t + ['-' + a if i != 0 else a for i, a in enumerate(x.split('-'))]
        else:
            t.append(x)

    for x in t:
        if '^' in x:
            t = x.split('x^')
            if len(t[0]) == 0:
                a = 1
            else:
                a = int(t[0])
            b = int(t[1])
        else:
            if 'x' in x:
                if x == 'x':
                    a = 1
                elif x == '-x':
                    a = -1
                else:
                    a = int(x[:-1])
                b = 1
            else:
                a = int(x)
                b = 0

        poly.append((a, b))

    return poly

def calc_yaku(n):
    ret = []
    for i in range(n + 1):
        if i != 0 and n % i == 0:
            ret.append(i)

    return reversed(sorted(ret + [-x for x in ret]))

def calc(poly, x):
    ret = 0
    for p in poly:
        ret += p[0] * x ** p[1]

    return ret


def solve(S):
    poly = parse(S)
    n = abs(poly[-1][0])
    yaku = calc_yaku(n)

    ans = []
    for x in yaku:
        if calc(poly, x) == 0:
            ans.append(-x)

    for x in ans:
        if x > 0:
            print('(x+{})'.format(x), end='')
        else:
            print('(x{})'.format(x), end='')

    print('')

S=input()
solve(S)

Submission status: Accepted

Solution code:
import copy
s = input()
k = [0] * 6
t = []
while True:
    i = 0
    if "+" in s[1:]:
        i = 1 + s[1:].index("+")
    if "-" in s[1:]:
        if i > 0:i = min(i, 1 + s[1:].index("-"))
        else:i = 1 + s[1:].index("-")
    if i == 0:
        k[0] = int(s)
        break
    j = s.index("x")
    if j + 3 == i:
        if j == 0:k[int(s[j + 2])] = 1
        else:k[int(s[j + 2])] = int(s[:j])
    else:
        if j == 0:k[1] = 1
        elif j == 1:k[1] = int(s[0] + "1")
        else:k[1] = int(s[:j])
    s = s[i:]
while True:
    if k[-1] == 0:k.pop()
    else:break
while True:
    i = 1
    while i <= abs(k[0]):
        if k[0] % i == 0:
            j = k[0] // i
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
            j *= -1
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
        i += 1
    if len(k) == 2:
        t.append(k[0])
        break
t.sort()
s = ""
for i in t:s += "(x{})".format(i) if i < 0 else "(x+{})".format(i)
print(s)

Submission status: Accepted

Solution code:
S = input().replace('+x', '+1x').replace('-x', '-1x').replace('^', '**').replace('x', '*1*(x)')[1:]
for i in range(2000, -2001, -1):
    if i == 0: continue

    T = S.replace('x', str(i))
    #print(T, eval(T))
    if eval(T) == 0:
        print('(x{:+})'.format(-i), end='')
else:
    print()

Submission status: Accepted

Solution code:
#E
import re
s = "+"+input()
c = 0
k = [0 for i in range(6)]
while c<len(s):
    find_1 = re.search(r'^([\+\-])x\^([2-5])', s[c:])
    if find_1:
        k[int(find_1.group(2))] = int(str(find_1.group(1))+"1")
        c += find_1.end()
        continue
    find_2 = re.search(r'^([\+\-][1-9][0-9]*)x\^([2-5])', s[c:])
    if find_2:
        k[int(find_2.group(2))] = int(str(find_2.group(1)))
        c += find_2.end()
        continue
    find_3 = re.search(r'^([\+\-][1-9][0-9]*)x', s[c:])
    if find_3:
        k[1] = int(str(find_3.group(1)))
        c += find_3.end()
        continue
    find_4 = re.search(r'^([\+\-])x', s[c:])
    if find_4:
        k[1] = int(str(find_4.group(1))+"1")
        c += find_4.end()
        continue
    find_5 = re.search(r'^([\+\-][1-9][0-9]*)', s[c:])
    if find_5:
        k[0] = int(str(find_5.group(1)))
        c += find_5.end()
        continue

#print(k)
#
ans = ""
que = list(range(abs(k[0]), -abs(k[0])-1, -1))
#print(que)

while True:
    buf = [0 for i in range(6)]
    n = que[0]
    p = 5
    while(k[p] == 0): p-=1
#    print(p)
    if p==0: break
    buf[p] = k[p]
    while p>0:
        p -= 1
        buf[p] = k[p] + n * buf[p+1]
#    print(k)
#    print(buf)
    if buf[0] == 0:
        k = buf[1:]+[0]
        if n < 0:
            ans += "(x+"+str(-n)+")"
        else:
            ans += "(x"+str(-n)+")"
    else:
        que.pop(0)
print(ans)

Submission status: Accepted

Solution code:
import re

S = input()
S = S.replace('x', '*({0})')
S = S.replace('^', '**')
S = re.sub(r'([+-])\*', r'\1', S)[1:]
for i in range(2000, -2001, -1):
    if eval(S.format(i)) == 0:
        print('(x{:+})'.format(-i), end='')
else:
    print()

Submission status: Runtime Error

Solution code:
def parse(S):
    poly = []
    t = []
    for x in S.split('+'):
        if '-' in x:
            t = t + ['-' + a if i != 0 else a for i, a in enumerate(x.split('-'))]
        else:
            t.append(x)

    for x in t:
        if '^' in x:
            t = x.split('x^')
            if len(t[0]) == 0:
                a = 1
            else:
                a = int(t[0])
            b = int(t[1])
        else:
            if 'x' in x:
                a = int(x[:-1])
                b = 1
            else:
                a = int(x)
                b = 0

        poly.append((a, b))

    return poly

def calc_yaku(n):
    ret = []
    for i in range(n + 1):
        if i != 0 and n % i == 0:
            ret.append(i)

    return reversed(sorted(ret + [-x for x in ret]))

def calc(poly, x):
    ret = 0
    for p in poly:
        ret += p[0] * x ** p[1]

    return ret


def solve(S):
    poly = parse(S)
    n = abs(poly[-1][0])
    yaku = calc_yaku(n)

    ans = []
    for x in yaku:
        if calc(poly, x) == 0:
            ans.append(-x)

    for x in ans:
        if x > 0:
            print('(x+{})'.format(x), end='')
        else:
            print('(x{})'.format(x), end='')

    print('')

S=input()
solve(S)

Submission status: Runtime Error

Solution code:
def parse(S):
    poly = []
    t = []
    for x in S.split('+'):
        if '-' in x:
            t = t + ['-' + a if i != 0 else a for i, a in enumerate(x.split('-'))]
        else:
            t.append(x)

    for x in t:
        if '^' in x:
            t = x.split('x^')
            if len(t[0]) == 0:
                a = 1
            else:
                a = int(t[0])
            b = int(t[1])
        else:
            if 'x' in x:
                if x == 'x':
                    a = 1
                else:
                    a = int(x[:-1])
                b = 1
            else:
                a = int(x)
                b = 0

        poly.append((a, b))

    return poly

def calc_yaku(n):
    ret = []
    for i in range(n + 1):
        if i != 0 and n % i == 0:
            ret.append(i)

    return reversed(sorted(ret + [-x for x in ret]))

def calc(poly, x):
    ret = 0
    for p in poly:
        ret += p[0] * x ** p[1]

    return ret


def solve(S):
    poly = parse(S)
    n = abs(poly[-1][0])
    yaku = calc_yaku(n)

    ans = []
    for x in yaku:
        if calc(poly, x) == 0:
            ans.append(-x)

    for x in ans:
        if x > 0:
            print('(x+{})'.format(x), end='')
        else:
            print('(x{})'.format(x), end='')

    print('')

S=input()
solve(S)

Submission status: Runtime Error

Solution code:
import copy
s = input()
k = [0] * 6
t = []
while True:
    i = 0
    if "+" in s[1:]:
        i = 1 + s[1:].index("+")
    if "-" in s[1:]:
        if i > 0:i = min(i, 1 + s[1:].index("-"))
        else:i = 1 + s[1:].index("-")
    if i == 0:
        k[0] = int(s)
        break
    j = s.index("x")
    if j + 3 == i:
        if j == 0:k[int(s[j + 2])] = 1
        else:k[int(s[j + 2])] = int(s[:j])
    else:
        if j == 0:k[1] = 1
        else:k[1] = int(s[:j])
    s = s[i:]
while True:
    if k[-1] == 0:k.pop()
    else:break
while True:
    i = 1
    while i <= abs(k[0]):
        if k[0] % i == 0:
            j = k[0] // i
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
            j *= -1
            kn = copy.deepcopy(k)
            for l in range(len(kn) - 1):
                if kn[l] % j == 0:
                    kn[l + 1] -= kn[l] // j
                    kn[l] //= j
                else:
                    break
            else:
                if kn[-1] == 0:
                    kn.pop()
                    t.append(j)
                    k = copy.deepcopy(kn)
                    break
        i += 1
    if len(k) == 2:
        t.append(k[0])
        break
t.sort()
s = ""
for i in t:s += "(x{})".format(i) if i < 0 else "(x+{})".format(i)
print(s)

Submission status: Runtime Error

Solution code:
S = input().replace('^', '**').replace('x', '*1*(x)')[1:]
for i in range(2000, -2001, -1):
    if i == 0: continue

    T = S.replace('x', str(i))
    #print(T, eval(T))
    if eval(T) == 0:
        print('(x{:+})'.format(-i), end='')
else:
    print()

Submission status: Runtime Error

Solution code:
S = input().replace('+x', '+1x').replace('^', '**').replace('x', '*1*(x)')[1:]
for i in range(2000, -2001, -1):
    if i == 0: continue

    T = S.replace('x', str(i))
    #print(T, eval(T))
    if eval(T) == 0:
        print('(x{:+})'.format(-i), end='')
else:
    print()