{"id":4210,"date":"2018-12-18T22:13:30","date_gmt":"2018-12-18T19:13:30","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=4210"},"modified":"2018-12-27T17:58:26","modified_gmt":"2018-12-27T14:58:26","slug":"4210","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=4210","title":{"rendered":"e-olymp 1521. \u041e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446"},"content":{"rendered":"

\u0417\u0430\u0434\u0430\u0447\u0430<\/h1>\n

\u0418\u043c\u0435\u044f \u0434\u0432\u0430 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 $A$ \u0438 $B$, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c $C = AB$ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446:<\/p>\n

$$C_{ij} = \\sum_{k}A_{ik}{Bkj}$$<\/p>\n

\u0427\u0438\u0441\u043b\u043e \u043a\u043e\u043b\u043e\u043d\u043e\u043a \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 $A$ \u0434\u043e\u043b\u0436\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0442\u044c \u0441 \u0447\u0438\u0441\u043b\u043e\u043c \u0441\u0442\u0440\u043e\u043a \u043c\u0430\u0441\u0441\u0438\u0432\u0430 $B$. \u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0447\u0435\u0440\u0435\u0437 $rows(A)$ \u0438 $columns(A)$ \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0440\u043e\u043a \u0438 \u043a\u043e\u043b\u043e\u043d\u043e\u043a \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 $A.$ \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b $C$ (\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0440\u043e\u043a \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 $A$, \u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432 \u0441 $B$) \u0440\u0430\u0432\u043d\u043e $rows(A)$ $columns(B)$ $columns(A).$ \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 A \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 10 \u00d7 20, B \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 20 \u00d7 15, \u0442\u043e \u0434\u043b\u044f \u0438\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043e\u0432\u0435\u0440\u0448\u0438\u0442\u044c 10 \u00d7 15 \u00d7 20, \u0438\u043b\u0438 3000 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b $C.$<\/p>\n

\u041f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0430\u0442\u0440\u0438\u0446 \u043c\u043e\u0436\u043d\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u0438\u043c\u0435\u044e\u0442\u0441\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b $X$, $Y$ \u0438 $Z$, \u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c $XYZ$ \u043c\u043e\u0436\u043d\u043e \u043b\u0438\u0431\u043e \u043a\u0430\u043a $(XY)Z$, \u043b\u0438\u0431\u043e \u043a\u0430\u043a $X(YZ)$. \u041f\u0443\u0441\u0442\u044c $X$ \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 5 \u00d7 10, $Y$ \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 10 \u00d7 20, $Z$ \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 20 \u00d7 35. \u041f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0442\u0440\u0435\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0438\u0437 \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445:<\/p>\n

$(XY)Z$<\/p>\n

$5 \u00d7 20 \u00d7 10 = 1000$ \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b (XY), \u0438\u043c\u0435\u044e\u0449\u0435\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 $5 \u00d7 20.$
\n\u041f\u043e\u0442\u043e\u043c $5 \u00d7 35 \u00d7 20 = 3500$ \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430.
\n\u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439: $4500.$
\n$X(YZ)$<\/p>\n

$10 \u00d7 35 \u00d7 20 = 7000$ \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b (YZ), \u0438\u043c\u0435\u044e\u0449\u0435\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 $10 \u00d7 35.$
\n\u041f\u043e\u0442\u043e\u043c $5 \u00d7 35 \u00d7 10$ \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430.
\n\u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439: $8750.$
\n\u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 $(XY)Z$ \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439.<\/p>\n

\u041f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0435\u043c\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043d\u0430\u0439\u0442\u0438 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0438\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f. \u041e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u044b\u0445 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e.<\/p>\n

\u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435
\n\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0435\u043c\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 \u0412\u0430\u043c \u0431\u0443\u0434\u0443\u0442 \u0434\u0430\u043d\u044b \u043b\u0438\u0448\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043c\u0430\u0442\u0440\u0438\u0446. \u041a\u0430\u0436\u0434\u044b\u0439 \u0442\u0435\u0441\u0442 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 $n (n \\leq 10)$ \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0435\u043c\u044b\u0445 \u043c\u0430\u0442\u0440\u0438\u0446, \u0437\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0442 $n$ \u043f\u0430\u0440 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0449\u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043c\u0430\u0442\u0440\u0438\u0446 (\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0440\u043e\u043a \u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432); \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043c\u0430\u0442\u0440\u0438\u0446 \u0437\u0430\u0434\u0430\u044e\u0442\u0441\u044f \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0438\u0445 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f. \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0442\u0435\u0441\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 $n = 0$ \u0438 \u043d\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f.<\/p>\n

\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435
\n\u041f\u0443\u0441\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043f\u0440\u043e\u043d\u0443\u043c\u0435\u0440\u043e\u0432\u0430\u043d\u044b $A1, A2,\\ldots, An.$ \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0435\u0441\u0442\u0430 \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0435\u0433\u043e \u043d\u043e\u043c\u0435\u0440 \u0438 \u0441\u043a\u043e\u0431\u043e\u0447\u043d\u043e\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446. \u0422\u0435\u0441\u0442\u044b \u043d\u0443\u043c\u0435\u0440\u0443\u044e\u0442\u0441\u044f \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 1. \u0412\u044b\u0432\u043e\u0434 \u0434\u043e\u043b\u0436\u0435\u043d \u0441\u0442\u0440\u043e\u0433\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0444\u043e\u0440\u043c\u0430\u0442\u0443, \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u043c\u0443 \u0432 \u043f\u0440\u0438\u043c\u0435\u0440\u0435. \u0415\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u043e\u0440\u044f\u0434\u043a\u043e\u0432 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446, \u0432\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u043b\u044e\u0431\u043e\u0439 \u0438\u0437 \u043d\u0438\u0445.<\/p>\n

\u0422\u0435\u0441\u0442\u044b<\/h2>\n\n\n\n\n\n\n
\u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/td>\n\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/td>\n<\/thead>\n
\n3
\n1 5
\n5 20
\n20 1
\n3
\n5 10
\n10 20
\n20 35
\n6
\n30 35
\n35 15
\n15 5
\n5 10
\n10 20
\n20 25
\n0\n<\/td>\n		\nCase 1: (A1 x (A2 x A3))
\nCase 2: ((A1 x A2) x A3)
\nCase 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))\n<\/td>\n<\/tr>\n
\n10
\n653 273
\n273 692
\n692 851
\n851 691
\n691 532
\n532 770
\n770 690
\n690 582
\n582 519
\n519 633
\n0\n<\/td>\n		\nCase 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))\n<\/td>\n<\/tr>\n
2
\n11 12
\n12 33
\n7
\n1 5
\n5 28
\n28 19
\n19 2
\n2 10
\n10 1
\n1 12
\n4
\n10 29
\n29 133
\n133 8
\n8 15
\n0\n<\/td>\n		\nCase 1: (A1 x A2)
\nCase 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7)
\nCase 3: ((A1 x (A2 x A3)) x A4)\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\u041a\u043e\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b<\/h2>\n
import java.util.Scanner;\r\n\r\npublic class Main {\r\n    private static class Matrix {\r\n        private int width;\r\n        private int height;\r\n\r\n        public Matrix(int width, int height) {\r\n            this.width = width;\r\n            this.height = height;\r\n        }\r\n    }\r\n\r\n    private static long multiple(long[][] dp, Matrix[] sizes, int[][] bestCut, int l, int r ) {\r\n        if (dp[l][r] == Long.MAX_VALUE) {\r\n            for (int i = l; i < r; i++) {\r\n            long cur = multiple(dp, sizes, bestCut, l, i) + multiple(dp, sizes, bestCut, i + 1, r) + sizes[l].width * sizes[i].height * sizes[r].height;\r\n                if (cur < dp[l][r]) {\r\n                    dp[l][r] = cur;\r\n                    bestCut[l][r] = i;\r\n                }\r\n            }\r\n        }\r\n        return dp[l][r];\r\n    }\r\n\r\n    private static void print(int l, int r, int[][] bestCut) {\r\n        if (l == r) {\r\n            System.out.print(\"A\" + (l + 1));\r\n        }\r\n        else {\r\n            System.out.print(\"(\");\r\n            print(l, bestCut[l][r], bestCut);\r\n            System.out.print(\" x \");\r\n            print(bestCut[l][r] + 1, r, bestCut);\r\n            System.out.print(\")\");\r\n        }\r\n    }\r\n    public static void main(String[] args) {\r\n        Scanner sc = new Scanner(System.in);\r\n        for (int c = 1, n = sc.nextInt(); n != 0; n = sc.nextInt(), c++) {\r\n            long[][] dp = new long[n][n];\r\n            for (int i = 0; i < n; i++) {\r\n                for (int j = 0; j < n; j++) {\r\n                    dp[i][j] = Long.MAX_VALUE;\r\n                }\r\n            }\r\n            Matrix[] sizes = new Matrix[n];\r\n            int[][] bestCut = new int[n][n];\r\n            for (int i = 0; i < n; i++) {\r\n                for (int j = 0; j < n; j++) {\r\n                    bestCut[i][j] = Integer.MAX_VALUE;\r\n                }\r\n            }\r\n            for (int i = 0; i < n; i++) {\r\n                int width = sc.nextInt();\r\n                int height = sc.nextInt();\r\n                sizes[i] = new Matrix(width, height);\r\n            }\r\n            for (int i = 0; i < n; i++) {\r\n                dp[i][i] = 0;\r\n            }\r\n            multiple(dp, sizes, bestCut, 0, n-1);\r\n            System.out.print(\"Case \" + c + \": \");\r\n            print(0, n - 1, bestCut);\r\n            System.out.println();\r\n        }\r\n    }\r\n}<\/pre>\n
\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/h2>\n
\u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446 ${\\displaystyle A_{i}A_{(i+1)}…A_{j}}$ ${\\displaystyle A_{i}A_{(i+1)}…A_{j}}$ \u0447\u0435\u0440\u0435\u0437 ${\\displaystyle A_{i..j}}$ ${\\displaystyle A_{i..j}}$, \u0433\u0434\u0435 i\\leq j. \u0415\u0441\u043b\u0438 i<j, \u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u043e\u0435 k, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u0442 ${\\displaystyle A_{i..j}}$ ${\\displaystyle A_{i..j}}$ \u043c\u0435\u0436\u0434\u0443 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c\u0438 ${\\displaystyle A_{k}}$ A_k \u0438 ${\\displaystyle A_{k+1}}$ A_${{k+1}}$, i\\leq k<j. \u0422\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f ${\\displaystyle A_{i..j}}$ ${\\displaystyle A_{i..j}}$ \u043d\u0430\u0434\u043e \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c ${\\displaystyle A_{i..k}}$ ${\\displaystyle A_{i..k}}$, \u043f\u043e\u0442\u043e\u043c ${\\displaystyle A_{k+1..j}}$ ${\\displaystyle A_{k+1..j}}$ \u0438 \u0437\u0430\u0442\u0435\u043c \u0438\u0445 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0438\u0442\u044c. \u0412\u044b\u0431\u043e\u0440 $k$ \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u043e\u043c \u0440\u0430\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0441\u043a\u043e\u0431\u043e\u043a \u043c\u0435\u0436\u0434\u0443 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c\u0438. \u0412\u044b\u0431\u0440\u0430\u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 $k$ \u043c\u044b \u0441\u0432\u0435\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0434\u0432\u0443\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0430\u043c \u0434\u043b\u044f \u043c\u0430\u0442\u0440\u0438\u0446 ${\\displaystyle A_{i..k}}$ ${\\displaystyle A_{i..k}}$ \u0438 ${\\displaystyle A_{k+1..j}}$ ${\\displaystyle A_{k+1..j}}.$ \u041e\u0431\u044a\u044f\u0441\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e: \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446 ${\\displaystyle A_{i..j}}$ ${\\displaystyle A_{i..j}}$ \u043f\u0440\u0438 i=j \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u2014 \u044d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u0441\u0430\u043c\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u0430 ${\\displaystyle A_{i}}$ A_${i}.$ \u041f\u0440\u0438 \u043d\u0435\u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u044b \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0432\u0441\u0435 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b ${\\displaystyle A_{i..j}}$ ${\\displaystyle A_{i..j}}$ \u043d\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b ${\\displaystyle A_{i..k}}$ ${\\displaystyle A_{i..k}}$ \u0438 ${\\displaystyle A_{k+1..j}}$ ${\\displaystyle A_{k+1..j}}$, \u0438\u0449\u0435\u043c \u043a\u043e\u043b-\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u0447\u0442\u043e\u0431\u044b \u0438\u0445 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438 \u0437\u0430\u0442\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0435\u043c \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b ${\\displaystyle A_{i..j}}$ ${\\displaystyle A_{i..j}}.$ (\u041e\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b-\u0432\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u043f\u043e\u0442\u0440\u0430\u0447\u0435\u043d\u043d\u043e\u0435 \u043d\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447 + \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446 ${\\displaystyle A_{i..k}A_{k+1..j}}$ ${\\displaystyle A_{i..k}A_{k+1..j}}$). \u0421\u0447\u0438\u0442\u0430\u0435\u043c, \u0447\u0442\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u044b \u043c\u0430\u0442\u0440\u0438\u0446 \u0437\u0430\u0434\u0430\u043d\u044b \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 ${\\displaystyle p}$ p \u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0442\u0440\u0438\u0446\u044b ${\\displaystyle A_{i}}$ A_${i}$ \u0440\u0430\u0432\u0435\u043d ${\\displaystyle p_{i-1}\\times p_{i}}$ ${\\displaystyle p_{i-1}\\times p_{i}}.$ \u0411\u0443\u0434\u0435\u043c \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0442\u044c \u0432 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 m \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043f\u0435\u0440\u0435\u0441\u0447\u0435\u0442\u0430 \u0434\u043b\u044f \u0443\u0436\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0432\u0448\u0438\u0445\u0441\u044f \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447.<\/p>\n
\u0421\u0441\u044b\u043b\u043a\u0438<\/h2>\n
\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/a>
\n\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0430 e-olymp<\/a>
\n\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 e-olymp<\/a>
\n\u041a\u043e\u0434 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0430 Ideone<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
\u0417\u0430\u0434\u0430\u0447\u0430 \u0418\u043c\u0435\u044f \u0434\u0432\u0430 \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 $A$ \u0438 $B$, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c $C = AB$ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446: $$C_{ij} = \\sum_{k}A_{ik}{Bkj}$$ \u0427\u0438\u0441\u043b\u043e \u043a\u043e\u043b\u043e\u043d\u043e\u043a \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 $A$ \u0434\u043e\u043b\u0436\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0442\u044c \u0441 \u0447\u0438\u0441\u043b\u043e\u043c \u0441\u0442\u0440\u043e\u043a \u043c\u0430\u0441\u0441\u0438\u0432\u0430 $B$. \u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0447\u0435\u0440\u0435\u0437 $rows(A)$ \u0438 $columns(A)$ \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0440\u043e\u043a \u0438 \u043a\u043e\u043b\u043e\u043d\u043e\u043a \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 $A.$ \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u044b $C$ (\u0435\u0435 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":119,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[26],"tags":[348,564,565,566],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/4210"}],"collection":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/users\/119"}],"replies":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4210"}],"version-history":[{"count":18,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/4210\/revisions"}],"predecessor-version":[{"id":4466,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/4210\/revisions\/4466"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}