|Contests||Virtual Contests||Problems||Submit||Runs Status||Rank List||Forum|
The number of columns in the A array must be the same as the number of rows in the B array. Notationally, let's say that rows(A) and columns(A) are the number of rows and columns, respectively, in the A array. The number of individual multiplications required to compute the entire C array (which will have the same number of rows as A and the same number of columns as B) is then rows(A) columns(B) columns(A). For example, if A is a 10 × 20 array, and B is a 20 × 15 array, it will take 10 × 15 × 20, or 3000 multiplications to compute the C array.To perform multiplication of more than two arrays we have a choice of how to proceed. For example, if X, Y, and Z are arrays, then to compute X Y Z we could either compute (X Y) Z or X (Y Z). Suppose X is a 5 × 10 array, Y is a 10 × 20 array, and Z is a 20 × 35 array. Let's look at the number of multiplications required to compute the product using the two different sequences:
Given the size of each array in a sequence of arrays to be multiplied, you are to determine an optimal computational sequence. Optimality, for this problem, is relative to the number of individual multiplcations required.
3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0
Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
Note: Special judge problem, you may get "Wrong Answer" when output in wrong format.