P10692 [SNCPC2024] Expression Matrix

An $n \times m$ character matrix $a_{ij}$ is called a valid expression matrix if and only if it satisfies the following conditions. - The matrix contains only the characters '1', '+', and '*'. - The string formed by each row from left to right is a valid expression. - The string formed by each column from top to bottom is a valid expression. The weight of a valid expression matrix is defined as follows: evaluate all $n + m$ expressions formed by each row (left to right) and each column (top to bottom), and take the sum of their values. Find, among all valid $n \times m$ expression matrices, one with the minimum weight. If there are multiple minimum answers, you may output any one of them. We define a string $s$ to be a valid expression as follows. - If $s = \overbrace{111\dots111}^{\text{at least one }1}$, then $s$ is a valid expression. - If both $s$ and $t$ are valid expressions, then $s$ * $t$ is also a valid expression. - If both $s$ and $t$ are valid expressions, then $s$ + $t$ is also a valid expression.

The input consists of one line with two integers $n, m$ ($3 \leq n, m \leq 9$), separated by a space, representing the number of rows and columns of the matrix.

Output $n$ lines, each containing $m$ characters. The $j$-th character of the $i$-th line is $a_{ij}$, representing a matrix with the minimum weight. If there are multiple minimum answers, you may output any one of them.

For the sample, the weight of the matrix is $4488$. It can be proven that there is no matrix with a smaller weight. Translated by ChatGPT 5