{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\nh1,h2,h3,h4,h5,h6{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\tGiven two arrays \u003ci\u003eA\u003c/i\u003e and \u003ci\u003eB\u003c/i\u003e, we can determine the array \u003ci\u003eC\u003c/i\u003e \u003d \u003ci\u003eA\u003c/i\u003e \u003ci\u003eB\u003c/i\u003e using the standard definition of matrix multiplication:\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003ccenter\u003e\r\n\t\u003cimg src\u003d\"http://uva.onlinejudge.org/external/3/348img13.gif\" /\u003e\u003c/center\u003e\r\n\u003cp\u003e\r\n\tThe number of columns in the \u003ci\u003eA\u003c/i\u003e array must be the same as the number of rows in the \u003ci\u003eB\u003c/i\u003e array. \u003cspan data-scayt_word\u003d\"Notationally\" data-scaytid\u003d\"1\"\u003eNotationally\u003c/span\u003e, let\u0026#39;s say that \u003ci\u003erows\u003c/i\u003e(\u003ci\u003eA\u003c/i\u003e) and \u003ci\u003ecolumns\u003c/i\u003e(\u003ci\u003eA\u003c/i\u003e) are the number of rows and columns, respectively, in the \u003ci\u003eA\u003c/i\u003e array. The number of individual \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"2\"\u003emultiplications\u003c/span\u003e required to compute the entire \u003ci\u003eC\u003c/i\u003e array (which will have the same number of rows as \u003ci\u003eA\u003c/i\u003e and the same number of columns as \u003ci\u003eB\u003c/i\u003e) is then \u003ci\u003erows\u003c/i\u003e(\u003ci\u003eA\u003c/i\u003e) \u003ci\u003ecolumns\u003c/i\u003e(\u003ci\u003eB\u003c/i\u003e) \u003ci\u003ecolumns\u003c/i\u003e(\u003ci\u003eA\u003c/i\u003e). For example, if \u003ci\u003eA\u003c/i\u003e is a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline67\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img1.gif\" width\u003d\"54\" /\u003e array, and \u003ci\u003eB\u003c/i\u003e is a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline71\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img2.gif\" width\u003d\"55\" /\u003e array, it will take \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline73\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img3.gif\" width\u003d\"93\" /\u003e , or 3000 \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"3\"\u003emultiplications\u003c/span\u003e to compute the \u003ci\u003eC\u003c/i\u003e array.\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\tTo perform multiplication of more than two arrays we have a choice of how to proceed. For example, if \u003ci\u003eX\u003c/i\u003e, \u003ci\u003eY\u003c/i\u003e, and \u003ci\u003eZ\u003c/i\u003e are arrays, then to compute \u003ci\u003eX\u003c/i\u003e \u003ci\u003eY\u003c/i\u003e \u003ci\u003eZ\u003c/i\u003e we could either compute (\u003ci\u003eX\u003c/i\u003e \u003ci\u003eY\u003c/i\u003e) \u003ci\u003eZ\u003c/i\u003e or \u003ci\u003eX\u003c/i\u003e (\u003ci\u003eY\u003c/i\u003e \u003ci\u003eZ\u003c/i\u003e). Suppose \u003ci\u003eX\u003c/i\u003e is a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline103\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img4.gif\" width\u003d\"46\" /\u003e array, \u003ci\u003eY\u003c/i\u003e is a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline67\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img1.gif\" width\u003d\"54\" /\u003e array, and \u003ci\u003eZ\u003c/i\u003e is a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline111\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img5.gif\" width\u003d\"54\" /\u003e array. Let\u0026#39;s look at the number of \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"6\"\u003emultiplications\u003c/span\u003e required to compute the product using the two different sequences:\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t(\u003ci\u003eX\u003c/i\u003e \u003ci\u003eY\u003c/i\u003e) \u003ci\u003eZ\u003c/i\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e\r\n\t\t\u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline119\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img6.gif\" width\u003d\"143\" /\u003e \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"8\"\u003emultiplications\u003c/span\u003e to determine the product (\u003ci\u003eX Y\u003c/i\u003e), a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline123\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img7.gif\" width\u003d\"46\" /\u003e array.\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\tThen \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline125\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img8.gif\" width\u003d\"143\" /\u003e \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"9\"\u003emultiplications\u003c/span\u003e to determine the final result.\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\tTotal \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"10\"\u003emultiplications\u003c/span\u003e: 4500.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u003ci\u003eX\u003c/i\u003e (\u003ci\u003eY\u003c/i\u003e \u003ci\u003eZ\u003c/i\u003e)\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e\r\n\t\t\u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline133\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img9.gif\" width\u003d\"151\" /\u003e \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"14\"\u003emultiplications\u003c/span\u003e to determine the product (\u003ci\u003eY\u003c/i\u003e \u003ci\u003eZ\u003c/i\u003e), a \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline139\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img10.gif\" width\u003d\"55\" /\u003e array.\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\tThen \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline141\" height\u003d\"24\" src\u003d\"http://uva.onlinejudge.org/external/3/348img11.gif\" width\u003d\"142\" /\u003e \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"15\"\u003emultiplications\u003c/span\u003e to determine the final result.\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\tTotal \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"16\"\u003emultiplications\u003c/span\u003e: 8750.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\r\n\tClearly we\u0026#39;ll be able to compute (\u003ci\u003eX\u003c/i\u003e \u003ci\u003eY\u003c/i\u003e) \u003ci\u003eZ\u003c/i\u003e using fewer individual \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"23\"\u003emultiplications\u003c/span\u003e.\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\tGiven 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 \u003cspan data-scayt_word\u003d\"multiplications\" data-scaytid\u003d\"24\"\u003emultiplications\u003c/span\u003e required.\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003ch2\u003e\r\n\t\u003cfont color\u003d\"#0070E8\"\u003e\u003ca name\u003d\"SECTION0001001000000000000000\"\u003eInput\u003c/a\u003e\u003c/font\u003e\u003c/h2\u003e\r\n\u003cp\u003e\r\n\tFor each array in the multiple sequences of arrays to be multiplied you will be given only the dimensions of the array. Each sequence will consist of an integer \u003ci\u003eN\u003c/i\u003e which indicates the number of arrays to be multiplied, and then \u003ci\u003eN\u003c/i\u003e pairs of integers, each pair giving the number of rows and columns in an array; the order in which the dimensions are given is the same as the order in which the arrays are to be multiplied. A value of zero for \u003ci\u003eN\u003c/i\u003e indicates the end of the input. \u003ci\u003eN\u003c/i\u003e will be no larger than 10.\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003ch2\u003e\r\n\t\u003cfont color\u003d\"#0070E8\"\u003e\u003ca name\u003d\"SECTION0001002000000000000000\"\u003eOutput\u003c/a\u003e\u003c/font\u003e\u003c/h2\u003e\r\n\u003cp\u003e\r\n\tAssume the arrays are named \u003cimg align\u003d\"MIDDLE\" alt\u003d\"tex2html_wrap_inline157\" height\u003d\"25\" src\u003d\"http://uva.onlinejudge.org/external/3/348img12.gif\" width\u003d\"109\" /\u003e . Your output for each input case is to be a line containing a parenthesized expression clearly indicating the order in which the arrays are to be multiplied. Prefix the output for each case with the case number (they are sequentially numbered, starting with 1). Your output should strongly resemble that shown in the samples shown below. If, by chance, there are multiple correct sequences, any of these will be accepted as a valid answer.\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003ch2\u003e\r\n\t\u003cfont color\u003d\"#0070E8\"\u003e\u003ca name\u003d\"SECTION0001003000000000000000\"\u003eSample Input\u003c/a\u003e\u003c/font\u003e\u003c/h2\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cpre\u003e\r\n3\r\n1 5\r\n5 20\r\n20 1\r\n3\r\n5 10\r\n10 20\r\n20 35\r\n6\r\n30 35\r\n35 15\r\n15 5\r\n5 10\r\n10 20\r\n20 25\r\n0\u003c/pre\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003ch2\u003e\r\n\t\u003cfont color\u003d\"#0070E8\"\u003e\u003ca name\u003d\"SECTION0001004000000000000000\"\u003eSample Output\u003c/a\u003e\u003c/font\u003e\u003c/h2\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cpre\u003e\r\nCase 1: (\u003cspan data-scayt_word\u003d\"A1\" data-scaytid\u003d\"37\"\u003eA1\u003c/span\u003e x (\u003cspan data-scayt_word\u003d\"A2\" data-scaytid\u003d\"40\"\u003eA2\u003c/span\u003e x \u003cspan data-scayt_word\u003d\"A3\" data-scaytid\u003d\"43\"\u003eA3\u003c/span\u003e))\r\nCase 2: ((\u003cspan data-scayt_word\u003d\"A1\" data-scaytid\u003d\"38\"\u003eA1\u003c/span\u003e x \u003cspan data-scayt_word\u003d\"A2\" data-scaytid\u003d\"41\"\u003eA2\u003c/span\u003e) x \u003cspan data-scayt_word\u003d\"A3\" data-scaytid\u003d\"44\"\u003eA3\u003c/span\u003e)\r\nCase 3: ((\u003cspan data-scayt_word\u003d\"A1\" data-scaytid\u003d\"39\"\u003eA1\u003c/span\u003e x (\u003cspan data-scayt_word\u003d\"A2\" data-scaytid\u003d\"42\"\u003eA2\u003c/span\u003e x \u003cspan data-scayt_word\u003d\"A3\" data-scaytid\u003d\"45\"\u003eA3\u003c/span\u003e)) x ((\u003cspan data-scayt_word\u003d\"A4\" data-scaytid\u003d\"46\"\u003eA4\u003c/span\u003e x \u003cspan data-scayt_word\u003d\"A5\" data-scaytid\u003d\"47\"\u003eA5\u003c/span\u003e) x \u003cspan data-scayt_word\u003d\"A6\" data-scaytid\u003d\"48\"\u003eA6\u003c/span\u003e))\u003c/pre\u003e"}}]}