問題一覧 > 通常問題

No.1910 High Element on Grid

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 55
作問者 : chineristAC / テスター : tokusakurai HYEA LEE
お気に入りにしたユーザー ProblemId : 7139 / 自分の提出
問題文最終更新日: 2022-04-22 21:15:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 340 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。