問題一覧 > 通常問題

No.2339 Factorial Paths

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 47
作問者 : SSRSSSRS / テスター : ぷらぷら 👑 NachiaNachia
17 ProblemId : 6702 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-10 05:57:42

問題文

正の整数 $N$ が与えられます。正の整数 $H, W$ を自由に選び、以下の条件を全て満たす縦 $H$ マス、横 $W$ マスのマス目を構築してください。
ただし、上から $i$ 行目 ($1 \leq i \leq H$)、左から $j$ 列目 ($1 \leq j \leq W$) のマスをマス $(i,j)$ と表します。

  • $1 \leq H \leq 2\,000$
  • $1 \leq W \leq 2\,000$
  • それぞれのマスは、白または黒で塗られている。
  • マス $(1,1)$ からマス $(H,W)$ まで、白で塗られたマスのみを通り、右または下に $1$ マス移動することを繰り返して行く経路はちょうど $N!$ 通り存在する。
    • より厳密に言うと、マスの列 $(x_1, y_1), (x_2, y_2), \dots, (x_{H+W-1}, y_{H+W-1})$ であって、以下の条件を全て満たすものは $N!$ 通り存在する。
      • $(x_1,y_1)=(1,1)$
      • $(x_{H+W-1},y_{H+W-1})=(H,W)$
      • 各 $i \ (1 \leq i \leq H + W - 1)$ に対し、マス $(x_i, y_i)$ は白で塗られている。
      • 各 $i \ (1 \leq i \leq H + W - 2)$ に対し、$(x_{i+1}, y_{i+1})$ は $(x_i+1, y_i)$ または $(x_i,y_i+1)$ である。
    • ただし、$2$ つのマスの列が異なるとは、ある $i \ (1 \leq i \leq H+W-1)$ が存在して、$(x_i, y_i)$ が異なることとする。

入力

入力は以下の形式で標準入力から与えられます。

$N$

出力

標準出力に以下の形式で出力してください。

$H$ $W$
$S_{1,1}S_{1,2} \cdots S_{1,W}$
$S_{2,1}S_{2,2} \cdots S_{2,W}$
$\vdots$
$S_{H,1}S_{H,2} \cdots S_{H,W}$
ただし、$S_{i,j}$ ($1 \leq i \leq H, 1 \leq j \leq W$) はマス $(i,j)$ が白で塗られているなら .、黒で塗られているなら# です。
最後に改行してください。

制約

入力は以下の制約を満たします。

  • $1 \leq N \leq 400$
  • $N$ は整数である。

サンプル

サンプル1
入力
3
出力
3 3
...
...
...

経路はちょうど $3!=6$ 通り存在します。

サンプル2
入力
5
出力
6 6
....#.
......
..#...
......
#.....
......

経路はちょうど $5!=120$ 通り存在します。

サンプル3
入力
1
出力
3 4
..##
#..#
##..

$H$ と $W$ を最小化する必要はありません。

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