問題一覧 > 通常問題

No.1399 すごろくで世界旅行 (構築)

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 95
作問者 : CuriousFairy315CuriousFairy315 / テスター : yosswi414yosswi414
5 ProblemId : 3565 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-19 22:57:28

問題文

315さんは一人ボードゲームで遊んでいます。
このボードゲームでは $V$ 個の頂点と1個の駒、 $V \times V$ の大きさの格子に区切られた紙を用いて遊びます。
紙には数字が書かれており、上から $i$ 番目、左から $j$ 番目のマスに書かれた数字は $E_{i,j}$ です。
駒が頂点 $i$ に置かれており、 $E_{i,j}=1$ ならば、次のターンに駒を頂点 $j$ に動かすことができます。
315さんは毎ターン必ず駒を動かさなくてはいけません。
この時、適切に駒を動かすことで、どの頂点に駒が置かれた状態から開始しても $D$ ターン後に駒が置かれている頂点をどの頂点でも好きに選べるような紙への数字の書き方を一つ求めてください。
このような答えは複数ありますが、そのうち $E_{i,j}=1$ となる集合 $\{i, j\}$ の個数を最小にするもののみを正答として扱います。

入力

$V$ $D$

  • $1 \leq V \leq 1000$
  • $1 \leq D \leq 640000$
  • 入力は全て整数である

出力

$V\times V$ の大きさを持つ行列 $E$ を出力してください。
ただし、 $E_{i, j}$ は頂点 $i$ から頂点 $j$ へ駒を1ターンで動かせるならば1、そうでないならば0となります。
また、任意の $i, j$ について $E_{i, j} = E_{j, i}$ を満たす必要があります。
最後に改行してください。

サンプル

サンプル1
入力
3 3
出力
011
101
110

どの頂点からも、 $3$ 回の移動で任意の頂点に到達することができます。

  • $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$
  • $1 \rightarrow 2 \rightarrow 3 \rightarrow 2$
  • $1 \rightarrow 3 \rightarrow 2 \rightarrow 3$
  • $2 \rightarrow 1 \rightarrow 3 \rightarrow 1$
  • $2 \rightarrow 3 \rightarrow 1 \rightarrow 2$
  • $2 \rightarrow 3 \rightarrow 1 \rightarrow 3$
  • $3 \rightarrow 1 \rightarrow 2 \rightarrow 1$
  • $3 \rightarrow 2 \rightarrow 1 \rightarrow 2$
  • $3 \rightarrow 1 \rightarrow 2 \rightarrow 3$
この場合の $E_{i,j}=1$ となる集合 $\{i, j\}$ の個数は $\{1, 2\}, \{1, 3\}, \{2, 3\}$ の全 $3$ 個であり、これが最小です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。