prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem J:</font> Matrix Calculator</H1>3 4<p>5Dr. Jimbo, an applied mathematician, needs to calculate matrices all day for solving his own problems. In his laboratory, he uses an excellent application program for manipulating matrix expressions, however, he cannot use it outside his laboratory because the software consumes much of resources. He wants to manipulate matrices outside, so he needs a small program similar to the excellent application for his handheld computer. 6</p>7 8<p>9Your job is to provide him a program that computes expressions of matrices.10</p>11 12<p>13Expressions of matrices are described in a simple language. Its syntax is shown in Table J.1. Note that even a space and a newline have meaningful roles in the syntax.14</p>15 16<center>17<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculator">18</center>19 20<p>21The start symbol of this syntax is program that is defined as a sequence of assignments in Table J.1. Each assignment has a variable on the left hand side of an equal symbol ("<span>=</span>") and an expression of matrices on the right hand side followed by a period and a newline (<span>NL</span>). It denotes an assignment of the value of the expression to the variable. The variable (var in Table J.1) is indicated by an uppercase Roman letter. The value of the expression (<span>expr</span>) is a matrix or a scalar, whose elements are integers. Here, a scalar integer and a 1 &times; 1 matrix whose only element is the same integer can be used interchangeably.22</p>23 24<p>25An expression is one or more terms connected by "<span>+</span>" or "<span>-</span>" symbols. A term is one or more factors connected by "<span>*</span>" symbol. These operators ("<span>+</span>", "<span>-</span>", "<span>*</span>") are left associative.26</p>27 28<p>29A factor is either a primary expression (primary) or a "<span>-</span>" symbol followed by a factor. This unary operator "<span>-</span>" is right associative.30</p>31 32<p>33The meaning of operators are the same as those in the ordinary arithmetic on matrices: Denoting matrices by <i>A</i> and <i>B</i>, <i>A</i> + <i>B</i>, <i>A</i> - <i>B</i>, <i>A</i> * <i>B</i>, and -A are defined as the matrix sum, difference, product, and negation. The sizes of <i>A</i> and <i>B</i> should be the same for addition and subtraction. The number of columns of <i>A</i> and the number of rows of <i>B</i> should be the same for multiplication.34</p>35 36<p>37Note that all the operators +, -, * and unary - represent computations of addition, subtraction, multiplication and negation modulo <i>M</i> = 2<sup>15</sup> = 32768, respectively. Thus all the values are nonnegative integers between 0 and 32767, inclusive. For example, the result of an expression 2 - 3 should be 32767, instead of -1.38</p>39 40<p>41<span>inum</span> is a non-negative decimal integer less than <i>M</i>.42</p>43 44<p>45<span>var</span> represents the matrix that is assigned to the variable var in the most recent preceding assignment statement of the same variable.46</p>47 48<p>49<span>matrix</span> represents a mathematical matrix similar to a 2-dimensional array whose elements are integers. It is denoted by a <span>row-seq</span> with a pair of enclosing square brackets. <span>row-seq</span> represents a sequence of rows, adjacent two of which are separated by a semicolon. row represents a sequence of expressions, adjacent two of which are separated by a space character.50</p>51 52<p>53For example, <span>[1 2 3;4 5 6]</span> represents a matrix <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculatorE1" valign="middle">. The first row has three integers separated by two space characters, i.e. "1 2 3". The second row has three integers, i.e. "4 5 6". Here, the <span>row-seq</span> consists of the two rows separated by a semicolon. The matrix is denoted by the <span>row-seq</span> with a pair of square brackets.54</p>55 56<p>57Note that elements of a row may be matrices again. Thus the nested representation of a matrix may appear. The number of rows of the value of each expression of a row should be the same, and the number of columns of the value of each row of a <span>row-seq</span> should be the same.58</p>59<p>60For example, a matrix represented by61</p>62<pre>63             [[1 2 3;4 5 6] [7 8;9 10] [11;12];13 14 15 16 17 18]64</pre>65 66<p>67is <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculatorE2" valign="middle"> The sizes of matrices should be consistent, as mentioned above, in order to form a well-formed matrix as the result. For example, <span>[[1 2;3 4] [5;6;7];6 7 8]</span> is not consistent since the first row "<span>[1 2;3 4] [5;6;7]</span>" has two matrices (2 &times; 2 and 3 &times; 1) whose numbers of rows are different. <span>[1 2;3 4 5]</span> is not consistent since the number of columns of two rows are different.68</p>69 70<p>71The multiplication of 1 &times; 1 matrix and <i>m</i> &times; <i>n</i> matrix is well-defined for arbitrary <i>m</i> &gt; 0 and <i>n</i> &gt; 0, since a 1 &times; 1 matrices can be regarded as a scalar integer. For example, <span>2*[1 2;3 4]</span> and <span>[1 2;3 4]*3</span> represent the products of a scalar and a matrix <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculatorE3" valign="middle"> and <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculatorE4" valign="middle">. <span>[2]*[1 2;3 4]</span> and <span>[1 2;3 4]*[3]</span> are also well-defined similarly.72</p>73 74<p>75An indexed-primary is a primary expression followed by two expressions as indices. The first index is 1 &times; <i>k</i> integer matrix denoted by (<i>i</i><sub>1</sub> <i>i</i><sub>2</sub> ... <i>i<sub>k</sub></i>), and the second index is 1 &times; <i>l</i> integer matrix denoted by (<i>j</i><sub>1</sub> <i>j</i><sub>2</sub> ... <i>j<sub>l</sub></i>). The two indices specify the submatrix extracted from the matrix which is the value of the preceding primary expression. The size of the submatrix is <i>k</i> &times; <i>l</i> and whose (<i>a</i>, <i>b</i>)-element is the (<i>i<sub>a</sub></i>, <i>j<sub>b</sub></i>)-element of the value of the preceding primary expression. The way of indexing is one-origin, i.e., the first element is indexed by 1.76</p>77 78<p>79For example, the value of <span>([1 2;3 4]+[3 0;0 2])([1],[2])</span> is equal to 2, since the value of its primary expression is a matrix <span>[4 2;3 6]</span>, and the first index <span>[1]</span> and the second <span>[2]</span> indicate the (1, 2)-element of the matrix. The same integer may appear twice or more in an index matrix, e.g., the first index matrix of an expression <span>[1 2;3 4]([2 1 1],[2 1])</span> is <span>[2 1 1]</span>, which has two 1's. Its value is <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculatorE5" valign="middle">.80</p>81 82<p>83A <span>transposed-primary</span> is a primary expression followed by a single quote symbol ("<span>'</span>"), which indicates the transpose operation. The transposed matrix of an <i>m</i> &times; <i>n</i> matrix <i>A</i> = (<i>a<sub>ij</sub></i>) (<i>i</i> = 1, ..., <i>m</i> and <i>j</i> = 1, ... , <i>n</i>) is the <i>n</i> &times; <i>m</i> matrix <i>B</i> = (<i>b<sub>ij</sub></i>) (<i>i</i> = 1, ... , <i>n</i> and <i>j</i> = 1, ... , <i>m</i>), where <i>b<sub>ij</sub></i> = <i>a<sub>ji</sub></i>. For example, the value of <span>[1 2;3 4]'</span> is <img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_matrixCalculatorE6" valign="middle">.84</p>85 86 87 88<H2>Input</H2>89 90<p>91The input consists of multiple datasets, followed by a line containing a zero. Each dataset has the following format.92</p>93 94<p>95<i>n</i><br>96<i>program</i><br>97</p>98 99<p>100<i>n</i> is a positive integer, which is followed by a program that is a sequence of single or multiple 101lines each of which is an assignment statement whose syntax is defined in Table J.1. <i>n</i> indicates 102the number of the assignment statements in the program. All the values of vars are undefined at the beginning of a program.103</p>104<p>105You can assume the following:106</p>107 108<ul>109<li> 1 &le; <i>n</i> &le; 10,</li>110<li> the number of characters in a line does not exceed 80 (excluding a newline),</li>111<li>there are no syntax errors and semantic errors (e.g., reference of undefined <span>var</span>),</li>112<li> the number of rows of matrices appearing in the computations does not exceed 100, and</li>113<li> the number of columns of matrices appearing in the computations does not exceed 100.</li>114</ul>115 116 117<H2>Output</H2>118 119<p>120For each dataset, the value of the expression of each assignment statement of the program should be printed in the same order. All the values should be printed as non-negative integers less than <i>M</i>.121</p>122 123<p>124When the value is an <i>m</i> &times; <i>n</i> matrix <i>A</i> = (<i>a<sub>ij</sub></i>) (<i>i</i> = 1, ... ,<i>m</i> and <i>j</i> = 1, ... , <i>n</i>), <i>m</i> lines should be printed. In the <i>k</i>-th line (1 &le; <i>k</i> &le; <i>m</i>), integers of the <i>k</i>-th row, i.e., <i>a</i><sub><i>k</i>1</sub>, ... , <i>a</i><sub><i>kn</i></sub>, should be printed separated by a space.125</p>126 127<p>128After the last value of a dataset is printed, a line containing five minus symbols '<span>-----</span>' should be printed for human readability.129</p>130 131<p>132The output should not contain any other extra characters.133</p>134 135<H2>Sample Input</H2>136<pre>1371138A=[1 2 3;4 5 6].1391140A=[[1 2 3;4 5 6] [7 8;9 10] [11;12];13 14 15 16 17 18].1413142B=[3 -2 1;-9 8 7].143C=([1 2 3;4 5 6]+B)(2,3).144D=([1 2 3;4 5 6]+B)([1 2],[2 3]).1455146A=2*[1 2;-3 4]'.147B=A([2 1 2],[2 1]).148A=[1 2;3 4]*3.149A=[2]*[1 2;3 4].150A=[1 2;3 4]*[3].1512152A=[11 12 13;0 22 23;0 0 33].153A=[A A';--A''' A].1542155A=[1 -1 1;1 1 -1;-1 1 1]*3.156A=[A -A+-A;-A'([3 2 1],[3 2 1]) -A'].1571158A=1([1 1 1],[1 1 1 1]).1593160A=[1 2 -3;4 -5 6;-7 8 9].161B=A([3 1 2],[2 1 3]).162C=A*B-B*A+-A*-B-B*-A.1633164A=[1 2 3 4 5].165B=A'*A.166C=B([1 5],[5 1]).1673168A=[-11 12 13;21 -22 23;31 32 -33].169B=[1 0 0;0 1 0;0 0 1].170C=[(A-B) (A+B)*B (A+B)*(B-A)([1 1 1],[3 2 1]) [1 2 3;2 1 1;-1 2 1]*(A-B)].1713172A=[11 12 13;0 22 23;0 0 33].173B=[1 2].174C=------A((((B))),B)(B,B)''''''.1752176A=1+[2]+[[3]]+[[[4]]]+2*[[[[5]]]]*3.177B=[(-[([(-A)]+-A)])].1788179A=[1 2;3 4].180B=[A A+[1 1;0 1]*4;A+[1 1;0 1]'*8 A+[1 1;0 1]''*12].181C=B([1],[1]).182C=B([1],[1 2 3 4]).183C=B([1 2 3 4],[1]).184C=B([2 3],[2 3]).185A=[1 2;1 2].186D=(A*-A+-A)'(A'(1,[1 2]),A'(2,[1 2])).1870188</pre>189 190<H2>Output for the Sample Input</H2>191<pre>1921 2 31934 5 6194-----1951 2 3 7 8 111964 5 6 9 10 1219713 14 15 16 17 18198-----1993 32766 120032759 8 7201132020 420313 13204-----2052 327622064 82078 420832762 22098 42103 62119 122122 42136 82143 62159 12216-----21711 12 132180 22 232190 0 3322011 12 13 11 0 02210 22 23 12 22 02220 0 33 13 23 3322311 0 0 11 12 1322412 22 0 0 22 2322513 23 33 0 0 33226-----2273 32765 32283 3 3276522932765 3 32303 32765 3 32762 6 327622313 3 32765 32762 32762 623232765 3 3 6 32762 3276223332765 3 32765 32765 32765 323432765 32765 3 3 32765 327652353 32765 32765 32765 3 32765236-----2371 1 1 12381 1 1 12391 1 1 1240-----2411 2 327652424 32763 624332761 8 92448 32761 92452 1 3276524632763 4 624754 32734 3273824832752 32750 17424932598 186 32702250-----2511 2 3 4 52521 2 3 4 52532 4 6 8 102543 6 9 12 152554 8 12 16 202565 10 15 20 252575 125825 5259-----26032757 12 1326121 32746 2326231 32 327352631 0 02640 1 02650 0 126632756 12 13 32758 12 13 32573 32588 180 123 62 3272526721 32745 23 21 32747 23 32469 32492 276 28 33 1526831 32 32734 31 32 32736 32365 32396 372 85 32742 32767269-----27011 12 132710 22 232720 0 332731 227411 122750 22276-----2774027880279-----2801 22813 42821 2 5 62833 4 3 82849 2 13 1428511 12 3 1628612871 2 5 6288128932909291112924 32932 132941 22951 229632764 3276429732764 32764298-----299</pre>300 301