Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Matrix-chain Multiplication

  The goal of the matrix-chain multiplication problem is to find the most efficient way to multiply given $n$ matrices $M_1, M_2, M_3,...,M_n$.

  Write a program which reads dimensions of $M_i$, and finds the minimum number of scalar multiplications to compute the maxrix-chain multiplication $M_1M_2...M_n$.

Input

  In the first line, an integer $n$ is given. In the following $n$ lines, the dimension of matrix $M_i$ ($i = 1...n$) is given by two integers $r$ and $c$ which respectively represents the number of rows and columns of $M_i$.

Output

  Print the minimum number of scalar multiplication in a line.

Constraints

$1 \leq n \leq 100$

$1 \leq r, c \leq 100$

Sample Input 1

6
30 35
35 15
15 5
5 10
10 20
20 25

Sample Output 1

15125



Sample input:
6
30 35
35 15
15 5
5 10
10 20
20 25


Sample output:
15125

Submission status: Accepted

Solution code:
global memo

def find_memo(m,l):#memoのm行l列の値を返す.data
                            #data[l]から続くm+1個の要素からなる部分リスト
    if(memo[m][l]!=0):
        return memo[m][l]
    
    if(m<2):
        return memo[m][l]
    

    tmp_min=999999999
    for i in range(1,m):
        left=find_memo(i,l)
        right=find_memo(m-i,l+i)
        middle=memo[0][l]*memo[0][l+i]*memo[0][l+m]
        if(left + right + middle< tmp_min):
            tmp_min = left + right + middle
    memo[m][l]=tmp_min
    return tmp_min




tmp_min=9999999999
n=int(input())
memo=[[0]*(n+1-i) for i in range(n+1)]#memo[i][j]はdata[j]から続くi+1個の要素からなる部分リストの最小計算コストを表す

memo[0][0],memo[0][1]=map(int,input().split())
for i in range(2,n+1):
    dummy,memo[0][i]= map(int,input().split())

for i in range(n-1):
    memo[2][i] = memo[0][i]*memo[0][i+1]*memo[0][i+2]

print(find_memo(n,0))

Submission status: Accepted

Solution code:
n = int(input())
r = [0]*n
c = [0]*n
for i in range(n):
    r[i], c[i] = map(int, input().split())


# T[i][j]  stands for the minimum number of product operation (of real numbers)
# that has to be performed in calculating 
# the matrix chain product $M_i \times \dots \times M_j$
T = [[0]*n for _ in range(n)]

# p = j -i
for p in range(1, n):
    for i in range(n-p):
        j = i + p
        val = float("inf")
        for k in range(i,j):
            val_tmp = T[i][k] + T[k+1][j] + r[i]*c[k]*c[j]
            if val_tmp < val:
                val = val_tmp
        T[i][j] = val
        
print(T[0][n-1])

Submission status: Accepted

Solution code:
N = int(input())
R = [0]*N
C = [0]*N
for i in range(N):
    R[i], C[i] = map(int, input().split())

INF = 10**18
dp = [[INF]*N for i in range(N)]
for i in range(N):
    dp[i][i] = 0
for l in range(1, N):
    for i in range(N-l):
        a0 = R[i]
        c0 = C[i+l]
        dp[i][i+l] = min(a0*C[j]*c0 + dp[i][j] + dp[j+1][i+l] for j in range(i, i+l))
print(dp[0][N-1])

Submission status: Accepted

Solution code:
# Matrix Chain Multiplication
import sys

N = int(input())
p = [0] * (N + 1)
for i in range(N):
    p[i], p[i + 1] = map(int, input().split())

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for l in range(2, N + 1):
    for i in range(1, N - l + 2):
        j = i + l - 1
        dp[i][j] = sys.maxsize
        for k in range(i, j):
            dp[i][j] = min(dp[i][j],
                           dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j])

print(dp[1][N])

Submission status: Accepted

Solution code:
def multi_chain_multiplication(n, P):
    M = [[0]*(n+1) for _ in range(n+1)]

    if n > 1:
        for l in range(2, n+1):
            for i in range(1, n-l+2):
                j = i + l - 1
                M[i][j] = float('inf')
                for k in range(i, j):
                    M[i][j] = min(M[i][j], M[i][k] + M[k+1][j] + P[i-1] * P[k] * P[j])
        return M[i][j]
    else:
        return 0

def read_and_print_min_multiplication(n):
    P = [0] * (n+1)
    for i in range(n):
        A = [int(i) for i in input().split()]
        if i == 0:
            P[i] = A[0]
            P[i+1] = A[1]
        else:
            P[i+1] = A[1]
    print(multi_chain_multiplication(n, P))

n = int(input())
read_and_print_min_multiplication(n)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

from sys import maxsize


def irange(start, stop=None):
    if stop:
        return range(start, stop + 1)
    else:
        return range(start + 1)


def count(ms):
    n = len(ms)

    p = [0] * (n + 1)
    for i in range(n):
        p[i] = ms[i][0]
        p[i + 1] = ms[i][1]

    m = [[None] * (n + 1) for _ in irange(n)]
    for i in irange(1, n):
        m[i][i] = 0
    for l in irange(2, n):
        for i in irange(1, n - l + 1):
            j = i + l - 1
            m[i][j] = maxsize
            for k in irange(i, j - 1):
                m[i][j] = min(
                    m[i][j],
                    m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                )

    return m[1][n]


def main():
    n = int(input())

    m = []
    for _ in range(n):
        m.append(tuple(int(x) for x in input().split()))
    c = count(m)
    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
p0, p1 = list(map(int, input().split()))
p = [p0, p1]
for i in range(n-1):
    pi = list(map(int, input().split()))
    p.append(pi[1])
    
dp = [[10**10]*(n+2) for _ in range(n+2)]

for i in range(0, n+2):
    dp[i][i] = 0

for l in range(2,n+1):
    for i in range(1, n-l+2):
        j = i + l - 1
        for k in range(i, j):
            dp[i][j] = min([dp[i][j], 
              dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]])

print(dp[1][n])

Submission status: Accepted

Solution code:
import sys
def calc(i,j):
    if i == j:
        return 0
    elif j-i == 1:
        return A[i][0]*A[i][1]*A[j][1]
    else:
        if d[i][j]:
            return d[i][j]
        else:
            ret = sys.maxsize
            for k in range(i,j):
                tmp = calc(i,k)+calc(k+1,j)+A[i][0]*A[k][1]*A[j][1]
                if tmp < ret:
                    ret = tmp
            d[i][j] = ret
            return ret

n = int(input())
A = []
d = [[None for _ in range(n)] for _ in range(n)]
for i in range(n):
    a,b = [int(i) for i in input().split()]
    A.append((a,b))
print(calc(0,n-1))

Submission status: Accepted

Solution code:
n = int(input())
p = [0] * (n + 1)
for i in range(1, n + 1):
    r, c = [int(v) for v in input().split()]
    p[i-1] = r
    p[i] = c

N_MAX = 100
M_MAX = 1 << 21
m = [[-1] * (n+1) for i in range(n+1)]

for i in range(1, n + 1):
    m[i][i] = 0

for l in range(2, n+1):
    for i in range(1, n - l + 2):
        j = i + l - 1
        m[i][j] = M_MAX
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print(m[1][n])

Submission status: Accepted

Solution code:
n = int(input())
c = [0] * (n+1)

c[0], c[1] = map(int, input().split())

for i in range(2, n+1):
    c[i] = int(input().split()[1])
 
array = [[10**7]*(n+1) for i in range(n+1)]
 
for i in range(1, n+1):
    array[i][i] = 0
 
for l in range(2, n+1):
    for i in range(1, n-l+2):
        j = i+l-1
        for k in range(i, j):
            array[i][j] = min(array[i][j], array[i][k] + array[k+1][j] + c[i-1]*c[k]*c[j])
 
print(array[1][n])

Submission status: Accepted

Solution code:
import sys
 
n = int(input())
 
mlist = [0]*(n+1)
#print(mlist)
mlist[0],mlist[1] = map(int,input().split())
#print(mlist)
for i in range(2,n+1):
    mlist[i] = int(input().split()[1])
    #print(mlist)
dp = [[sys.maxsize]*(n+1) for i in range(n+1)]
 
for i in range(1,n+1):
    dp[i][i] = 0
 
for l in range(2,n+1) :
    for i in range(1,n-l+2):
        j = i +l - 1
        for k in range(i,j):
            dp[i][j] = min(dp[i][j],dp[i][k]+
                           dp[k+1][j]+mlist[i-1]*mlist[k]*mlist[j])
 
print(dp[1][n])

Submission status: Accepted

Solution code:
# Dynamic Programming - Matrix Chain Multiplication
INFTY = float('inf')
MAX = 200
size = int(input())
# 1???????????§??????
C = [[INFTY for _ in range(MAX+1)] for i in range(MAX+1)]
R = [0 for i in range(MAX+2)]
for i in range(size):
    a,b = map(int, input().split())
    if i == 0:
        R[1] = a
    R[i+2] = b

for i in range(1, size+1): C[i][i] = 0

for j in range(1,size):
    for i in range(1,size):
        for k in range(i+1,i+j+1):
            cost = C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]
            if cost < C[i][i+j]:
                C[i][i+j] = cost
print(C[1][size])

Submission status: Runtime Error

Solution code:
import sys, itertools

n = int(sys.stdin.readline())
MM = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

amin = 0
m = MM[0][:]
for i in range(n-1):
    amin += m[0]*m[1]*MM[i+1][1]
    m[1]=MM[i+1][1]


for t in itertools.permutations(range(n-1), n-2):

    mm=[m[:] for m in MM]
    o = list(t)
    ans=0
    for _ in range(n-2):
        i = o.pop(0)
        ans += mm[i][0]*mm[i+1][1]*mm[i][1]
        if ans>amin: break
        mm[i][1] = mm[i+1][1]
        mm.pop(i+1)
        
        for j in range(len(o)):
            if o[j]>i: o[j] -=1
    else:
        ans += mm[0][0]*mm[0][1]*mm[1][1]
        if amin>ans: amin=ans


print(amin)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
debug = False
import numpy as np
def dprint(*objects):
    if debug == True:
        print(*objects)

# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())



def solve():
    n = int(input())
    mat_list = []
    for i in range(n):
        mat_list.append(list(map(int, input().split())))
    dprint(mat_list)

    # 掛け始めのidxと掛け終わりのidxをi, jとし、計算回数を持つメモ
    memo = np.zeros(shape=(n, n))

    def calc(start, end):
        dprint("*", start, end)
        # 1つの行列なら0
        if end == start:
            return 0

        # メモがあれば返す
        if memo[start][end] != 0:
            return memo[start][end]

        # 2つの行列なら、答えを計算しメモ追記
        if end - start == 1:
            cost = mat_list[start][0] * mat_list[start][1] * mat_list[end][1]
            memo[start][end] = cost
            dprint(start, end, cost)
            return cost

        # 3つ以上なら、再帰
        min_cost = -1
        if end - start >= 2:
            for right_start in range(start+1, end+1):
                left = calc(start, right_start-1)
                right = calc(right_start, end)
                cost = left + right + mat_list[start][0] * mat_list[right_start][0] * mat_list[end][1]
                if min_cost == -1 or min_cost > cost:
                    min_cost = cost
                dprint(start, end, right_start, min_cost, cost)

        memo[start][end] = min_cost
        return min_cost

    ans = calc(0, n-1)
    dprint(memo)
    print(int(ans))

solve()

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
rc = [list(map(int, input().split())) for _ in range(n)]
rc_min = rc.index(min(rc))

def calc(rc):
    total = 0
    for i, irc in enumerate(rc):
        if i ==0:
            r, c = irc
        else:
            total += r * c * irc[1]
            c = irc[1]
    return r, c, total
def reverse_calc(rc):
    total = 0
    for i, irc in enumerate(rc[::-1]):
        if i ==0:
            r, c = irc
        else:
            total += r * c * irc[0]
            r = irc[0]
    return r, c, total

total = 0
r1, c1, ret = reverse_calc(rc[:rc_min])
total += ret
r2, c2, ret =calc(rc[rc_min:])
total += ret
total += r1 * c1 * c2
print(total)

Submission status: Runtime Error

Solution code:
def solve():
    a = raw_input()
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = raw_input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
     
print solve(M)

Submission status: Runtime Error

Solution code:
def solve():
    a = raw_input()
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
     
print solve(M)

Submission status: Runtime Error

Solution code:
def solve():
    a = raw_input()
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
     
print solve()

Submission status: Runtime Error

Solution code:
def solve(a):
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = raw_input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
print solve(M)

Submission status: Runtime Error

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n)] for j in range(n)]
  
  for l in range(2, n):
    for i in range(1, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j-1))
  
  return m[0][n-1]

n = input()
for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Runtime Error

Solution code:
def mcm(M):
  n = len(M)
  m = [[0 for i in range(n+1)] for j in range(n+1)]
  
  for l in range(2, n):
    for i in range(1, n-l+1):
      j = i + l - 1
      def cost(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(cost(i, k, j) for k in range(i, j-1))
  
  return m[0][n-1]

n = input()
for i in range(n):
  M.append(map(int, raw_input().split()))
print mcm(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d)
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(0,n+1+long):
  k=i+long-1
  def f(i,j,k):
   return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print solve(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d)
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(0,n+1-long):
  k=i-1+long
  def f(i,j,k):
   return A[i][j-1]+A[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print solve(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d)
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(0,n+1-long):
  k=i-1+long
  def f(i,j,k):
   return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance (M)

Submission status: Runtime Error

Solution code:
def edit_distance(d)
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(0,n+1-long):
  k=i-1+long
  def f(i,j,k):
   return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
  A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d)
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(2, n+1):
  for long in range(0,n+1-long):
   k=i-1+long
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
  return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d):
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(2, n+1):
  for long in range(0,n+1-long):
   k=i-1+long
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
  return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d):
 n =len(d)
 A=[[0 for i in range(n)] for j in range(n)]
 for long in range(2, n+1):
  for i in range(0,n+1-long):
   k=i-1+long
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
  return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance(M)

Submission status: Runtime Error

Solution code:
def edit_distance(d):
 n =len(d)
 A=[[0 for i inrange(n)] for j in range(n)]
 for long in range(2, n+1):
  for i in range(0,n+1-long):
   k=i-1+long
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
  return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance(M)

Submission status: Runtime Error

Solution code:
def edit_distance(a):
 n = len(a)
 A = [[0 for i in range(n)] for j in range(n)]
 for long in range(2, n+1):
  for i in range(0, n-long+1):
   k = i+long-1
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distace(M)

Submission status: Runtime Error

Solution code:
def edit_distance(a):
 n = len(a)
 A = [[0 for i in range(n)] for j in range(n)]
 for long in range(2, n+1):
  for i in range(0, n-long+1):
   k = i+long-1
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distace(M)

Submission status: Runtime Error

Solution code:
def edit_distance(M):
 n = len(M)
 A = [[0 for i in range(n)] for j in range(n)]
 for long in range(2, n+1):
  for i in range(0, n-long+1):
   k = i+long-1
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distace(M)

Submission status: Runtime Error

Solution code:
def edit_distance(M):
 n = len(M)
 A = [[0 for i in range(n)] for j in range(n)]
 for l in range(2, n+1):
  for i in range(0, n-l+1):
   k = i+l-1
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distace(M)

Submission status: Runtime Error

Solution code:
def edit_distance(M):
 n = len(M)
 A = [[0 for i in range(n)] for j in range(n)]
 for l in range(2, n+1):
  for i in range(0, n-l+1):
   k = i+l-1
   def f(i,j,k):
    return A[i][j]+A[j+1][k] + M[i][0]*M[j][1]*M[k][1]
   A[i][k] = min(f(i,j,k) for j in range(i,k))
 return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distace(M)

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [ [ 0 for i in range(n) ] for j in range(n) ]
for i in xrange(n):
  M.append( map ( int , raw_input().split() ) )


for l in xrange( 2,n+1 ):
  for i in xrange( 0,n-l+1 ):
    j = i + l - 1
    m[i][j] = min( cost( i,k,j ) for k in xrange( i,j ) )
 
print m[0][n-1]

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [ [ 0 for i in range(n) ] for j in range(n) ]
for i in xrange(n):
  M.append( map ( int , raw_input().split() ) )

n = len(p)
for l in xrange( 2,n+1 ):
  for i in xrange( 0,n-l+1 ):
    j = i + l - 1
    m[i][j] = min( cost( i,k,j ) for k in xrange( i,j ) )
 
print m[0][n-1]

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [ [ 0 for i in range(n) ] for j in range(n) ]
for i in xrange(n):
  M.append( map ( int , raw_input().split() ) )

for l in range( 2,n+1 ):
  for i in range( 0,n-l+1 ):
    j = i + l - 1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][n-1]

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [ [ 0 for i in range(n) ] for j in range(n) ]
for i in range(n):
  M.append( map ( int , raw_input().split() ) )

p_long = len(p)
for l in range( 2,n+1 ):
  for i in range( 0,n-l+1 ):
    j = i + l - 1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][p_long-1]

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [ [ 0 for i in range(n) ] for j in range(n) ]
for i in range(n):
  M.append( map ( int , raw_input().split() ) )

M_long = len(M)
for l in range( 2,n+1 ):
  for i in range( 0,n-l+1 ):
    j = i + l - 1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][M_long-1]

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [ [ 0 for i in range(n) ] for j in range(n) ]
for i in range(n):
  M.append( map ( int , raw_input().split() ) )

M_long = len(M)
for x in range( 2,M_long+1 ):
  for i in range( 0,M_long-x+1 ):
    j = i + x - 1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][M_long-1]

Submission status: Runtime Error

Solution code:
n = input()

def scalar(n):
   for i in range(0, len(n)):
      for j in range(0, len(n)):
         m[i][j] = 0

   for l in range(2, len(n)):
      for i in range(0, len(n)):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))

   print m[0][len(n)-1]

for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

Submission status: Runtime Error

Solution code:
n = input()
 
def scalar(n):
   m = [[for i in range(0, len(n))] for j in range(0, len(n))]
 
   for l in range(2, len(n)):
      for i in range(0, len(n)):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))
 
   print m[0][len(n)-1]
 
for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

Submission status: Runtime Error

Solution code:
n = input()
  
def scalar(n):
   m = [[0 for i in range(len(n))] for j in range(len(n))]
  
   for l in range(2, len(n)):
      for i in range(0, len(n)):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))
  
   print m[0][len(n)-1]
  
for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [[ 0 for i in range(n) ] for j in range(n) ]
for i in range(n):
  M.append( map (int, raw_input().split() ) )
 
M_long = len(M)
for l in range( 2,M_long+1 ):
  for i in range( 0,M_long-l+1 ):
    j = i+l-1
    m[i][j] = min( cost( i,k,j ) for k in range( i,j ) )
 
print m[0][M_long-1]

Submission status: Runtime Error

Solution code:
n = input()
??????
def scalar(n):
??????m = [[0 for i in range(len(n))] for j in range(len(n))]
??????
??????for l in range(2, len(n)+1):
????????????for i in range(0, len(n)-l+1):
??????????????????j = i + l - 1
??????????????????m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))
??????
??????print m[0][len(n)-1]
??????
for i in range(n):
??????M.append(map(int, raw_input().split()))
scalar(M)

Submission status: Runtime Error

Solution code:
def cost( i,k,j ):
  return m[i][k] + m[k+1][j] + p[i][0] * p[k][1] * p[j][1]
 
n = input()
M = []
m = [[ 0 for i in xrange(n) ] for j in xrange(n) ]
for i in xrange(n):
  M.append( map (int, raw_input().split() ) )
 
M_long = len(M)
for l in xrange( 2,M_long+1 ):
  for i in xrange( 0,M_long-l+1 ):
    j = i+l-1
    m[i][j] = min( cost( i,k,j ) for k in xrange( i,j ) )
 
print m[0][M_long-1]

Submission status: Runtime Error

Solution code:
n = input()

def scalar(n):
   m = [[0 for i in range(len(n))] for j in range(len(n))]

   for l in range(2, len(n)+1):
      for i in range(0, len(n)-l+1):
         j = i + l - 1
         m[i][j] = min(m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1] for k in range(i, j))

   print m[0][len(n)-1]

for i in range(n):
   M.append(map(int, raw_input().split()))
scalar(M)

Submission status: Runtime Error

Solution code:
n = input()
r = [0 for row in range(100)]
c = [0 for row in range(100)]
m = [[0 for col in range(n)] for row in range(n)]
for i in range(n-1):
  p[i], p[i+1] = map(int, raw_input().split())

for l in range(2, n):
  for i in range(n-1):
    j = i + l - 1
    m[i][j] = 100000000000
    for k in range(j-1):
      if m[i][j]>m[i][k]+m[i][k]+m[k+1][j]+p[i-1]*p[k]*[j]:
        m[i][j] = m[i][k]+m[i][k]+m[k+1][j]+p[i-1]*p[k]*[j]

print m[1][n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())
p = [0 for i in xrange(1, 101)]
m = [0 for i in xrange(1, 101)] for j in range(1, 101)

for i in xrange(1, n+1):
    p[n-1],p[n] = map(int, raw_input.split())

for k in xrange(2, n+1):
    for i in range(1, n-k+2):
       j = i+k-1
       m[i][j] = float("inf")
       for l in range(i,j):
          m[i][j] =  min(m[i][j], m[i][l]+m[l+1][j]+p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())
p = [0 for i in xrange(0, 101)]
m = [0 for i in xrange(0, 101)] for j in range(0, 101)

for i in xrange(1, n+1):
    p[n-1],p[n] = map(int, raw_input.split())

for k in xrange(2, n+1):
    for i in range(1, n-k+2):
       j = i+k-1
       m[i][j] = float("inf")
       for l in range(i,j):
          m[i][j] =  min(m[i][j], m[i][l]+m[l+1][j]+p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [0 for i in range(0, 101)] for j in range(0, 101)

for i in range(1, n+1):
    p[n-1],p[n] = map(int, raw_input.split())

for k in range(2, n+1):
    for i in range(1, n-k+2):
       j = i+k-1
       m[i][j] = float("inf")
       for l in range(i,j):
          m[i][j] =  min(m[i][j], m[i][l]+m[l+1][j]+p[i-1]*p[l]*p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = input()
for i in range(1,n+1):
  m[i][i] = 0

  p[i-1], p[i] = map(int, input().split())

for m in range(2,n+1):
  for i in range(1,n-m+1+1):
    j = i + m - 1
    m[i][j] = 999999999999999
    for k in range(i,j-1+1):
      m[i][j] = min(m[i][j], m[i][k] + m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = input()
for i in range(1,n+1):
  m[i][i] = 0

  p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
  for i in range(1,n-m+1+1):
    j = i + m - 1
    m[i][j] = 999999999999999
    for k in range(i,j-1+1):
      m[i][j] = min(m[i][j], m[i][k] + m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = input()
p = [0 for raw in range(101)]
m = [[0 for col in range(n+1)] for row in range(n+1)] 
for i in range(1,n+1):
  m[i][i] = 0

  p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
  for i in range(1,n-m+1+1):
    j = i + m - 1
    m[i][j] = 999999999999999
    for k in range(i,j-1+1):
      m[i][j] = min(m[i][j], m[i][k] + m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = input()
p = [0 for raw in range(101)]
m = [[0 for col in range(n+1)] for row in range(n+1)] 
for i in range(1,n+1):
  m[i][i] = 0

  p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
  for i in range(1,n-m+1+1):
    j = i + m - 1
    m[i][j] = 999999999999999
    for k in range(i,j-1+1):
      m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)
for i in range(1, n + 1):
    p[i-1], p[i] = map(int, raw_input().split())
     
for l in range(2, n + 1):
    for i in range(1, n - l + 2):
        j = i + l - 1
        m[i][j] = float("inf")
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]* p[k] * p[j])
 
print m[1][n]

Submission status: Runtime Error

Solution code:
n = input()
p = [] 
for i in range(1,n+1):
 m[i][i] = 0
 p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
 for i in range(1,n-m+1+1):
  j = i + m - 1
  m[i][j] = 999999999999999
  for k in range(i,j-1+1):
   m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
def matrix(n):
    x = [[0 for i in range(n)] for j in range(n))]
    for l in range(2, len(n)+1):
        for i in range(0, len(n)-l+1):
            j = i + l - 1
            x[i][j] = min(x[i][k] + x[k+1][j] + X[i][0]*X[k][1]*X[j][1] for k in range(i, j))

    print x[0][len(n)-1]

n = input()
X = []

for i in range(n):
    X.append(map(int, raw_input().split()))

matrix(X)

Submission status: Runtime Error

Solution code:
n = int,input()
p = [] 
for i in range(1,n+1):
 m[i][i] = 0
 p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
 for i in range(1,n-m+1+1):
  j = i + m - 1
  m[i][j] = 999999999999999
  for k in range(i,j-1+1):
   m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())
p = [] 
for i in range(1,n+1):
 m[i][i] = 0
 p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
 for i in range(1,n-m+1+1):
  j = i + m - 1
  m[i][j] = 999999999999999
  for k in range(i,j-1+1):
   m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

Submission status: Runtime Error

Solution code:
n = int(raw_input())
p = []
m = []
for i in range(1,n+1):
 m[i][i] = 0
 p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
 for i in range(1,n-m+1+1):
  j = i + m - 1
  m[i][j] = 999999999999999
  for k in range(i,j-1+1):
   m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]