へいこうすう

数値シーケンスを2つの部分に分割して、この2つの部分の積が等しくなるように定義すると仮定します.このような数列は、1236のように、1*2*3=6で、平衡数です.ここで1つの数列を与えて、バランス数であるかどうかを判断します.分析:この問題には多くの解法があり、まず最初の最も原始的な考えは順次区切り記号を設定し、それから分割後の2つのサブ列の積を比較することであり、検査効率を高めるために、まず非完全な平方数、すなわち数字が開方した後に整数型の数字ではないことを濾過することができるが、このように計算の複雑さを増加させる.

 def balance_num_init():
    num = sys.stdin.readline().strip()
    if len(num)==0:
        print "YES"
        return
    #if isinstance(math.sqrt(num),int):
    for i in xrange(1,len(num)):
            p1 = num[:i]
            p2 = num[i:]
            pro1,pro2 = 1,1
            for j in range(len(p1)):
                pro1 = pro1*int(p1[j])
            for j in range(len(p2)):
                pro2 = pro2*int(p2[j])
            if pro1 ==pro2:
                print "YES"
                break
            else:
                pass
            if i==len(num)-1:
                print "NO"

積を計算するたびに、前のサブストリングの積を繰り返し計算するので、動的プランニングメソッドを使用して、計算した積を次回の使用のために保存することを考慮します.この方法では,分割点より前のすべての数の積と総積を先に算出し,次いで分割点より前のすべての数の積を総積で割って第2の部分積を得,両者が等しいか否かを判断できるかもしれないが,これによりかなりの空間と時間がかかる.したがって、数列逆シーケンスを考慮すると、得られた数列はダイナミックプランニングを用いて同様の計算を行う.すなわち、dp[i][j]を用いてi番目の位置の数字からj番目の位置の数字への積を表し、その後、2つの数列に対してそれぞれ前後および後から前への対比を行い、等しい比較があれば平衡数と判断することができ、コードは以下の通りである.この問題はもっと良い方法があるはずです.みんなで討論することを歓迎します.

def dp():
    num = sys.stdin.readline().strip()
    if len(num)==0:
        print "YES"
        return
    #prod = 1
    dp = [[0 for i in range(len(num))] for j in  range(len(num))]
    rdp = deepcopy(dp)
    for i in range(len(num)):
        dp[i][i] = int(num[i])
        rdp[i][i] = int(num[len(num)-1-i])
        #prod = prod*int(num[i])
    rnum = num[::-1]
    for k in range(len(num)):
        for j in xrange(k+1,len(num)):
            dp[k][j] = dp[k][j-1]*int(num[j])
    for k in range(len(num)):
        for j in xrange(k+1,len(num)):
            rdp[k][j] = rdp[k][j-1]*int(rnum[j])
            #if dp[k][j]*dp[k][j]==prod:   
    for j in xrange(1,len(num)):
        if dp[0][j]==rdp[0][len(num)-2-j] and len(num)-2-j>=0:
                print "YES"
                return
        if j==len(num)-1:
            print "NO"