No.1910 High Element on Grid
タグ : / 解いたユーザー数 55
作問者 :
Problem Statement
(21:15 Sample corrected)
In an integer sequence $X=(X_1,\ X_2,\ \dots,\ X_n)$ of length $n$, $X_i$ is called a "high element" if $X_j < X_i$ holds for every integer $j< i$.
You are given integer sequences $R=(R_1,\ R_2,\ \dots,\ R_H),\ C=(C_1,\ C_2,\ \dots,\ C_W)$ of lengths $H,\ W$. Here, $R_1=C_1=1$ holds.
Find $1$ matrix $A=(A_{i,j})_{1\le i \le H,\ 1\le j \le W}$ of size $H \times W$ satisfying the following conditions. It can be proved that, under the constraints of this problem, at least $1$ such $A$ exists.
Conditions- $1 \le A_{i,j} \le 10^9$
- For every $1\le i \le H$, the integer sequence $(A_{i,1},\ A_{i,2},\ \dots,\ A_{i,W})$ has exactly $R_i$ "high elements"
- For every $1 \le j \le W$, the integer sequence $(A_{1,j},\ A_{2,j},\ \dots,\ A_{H,j})$ has exactly $C_j$ "high elements"
Input
$H$ $W$ $R_1$ $R_2$ $\dots$ $R_H$ $C_1$ $C_2$ $\dots$ $C_W$
- $1 \le H,\ W \le 500$
- $1 \le R_i \le W$
- $1 \le C_j \le H$
- $R_1=C_1=1$
- All input values are integers
Output
Print $1$ matrix $A$ satisfying the conditions in the following format. If there are multiple such matrices, you may print any of them.
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$
Print a newline at the end.
Sample
Sample 1
Input
2 4 1 2 1 1 2 2
Output
6 3 4 1 5 2 8 2
The integer sequence $(A_{1,1},\ A_{1,2},\ A_{1,3},\ A_{1,4})=(6,\ 3,\ 4,\ 1)$ has $R_1=1$ "high element": $A_{1,1}=6$.
The integer sequence $(A_{2,1},\ A_{2,2},\ A_{2,3},\ A_{2,4})=(5,\ 2,\ 8,\ 2)$ has $R_2=2$ "high elements": $A_{2,1}=5,\ A_{2,3}=8$.
Thus, the $2$-nd condition is satisfied. It can be verified in the same way that the $3$-rd condition is also satisfied.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。