問題一覧 > 通常問題

No.3740 Troublesome Congestion

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 6
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13612 / 自分の提出
問題文最終更新日: 2026-11-02 04:29:30
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
グリッド構築24題 (順位表) の他の問題:

Problem Statement

You are developing a puzzle game and are trying to create a stage with a "just right" difficulty.

A stage is represented by a square grid and consists of $3$ types of cells: passage, wall, and switch. The player can move on passage cells or switch cells, but cannot enter wall cells.

Let the stage be a grid with $N$ rows and $N$ columns, and let $(i, j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left. Can you create a stage that satisfies all of the following conditions? Note that the size $N$ of the stage is not given in the input, and you may choose it freely.

  • $2 \leq N \leq 40$
  • Cells $(1, 1)$ and $(N, N)$ are passage cells
  • When the player travels from cell $(1, 1)$ to $(N, N)$ by repeatedly moving to the adjacent cell to the right or below, the number of paths that pass through a switch cell exactly $1$ time is exactly $M$

If it is possible, output one such stage; if it is impossible, output -1.

$T$ test cases are given, so output the answer for each of them.

Constraints

  • All inputs are integers
  • $1 \leq T \leq 100$
  • $1 \leq M \leq 10^{18}$

Partial Score

This problem has partial scoring based on subtasks.

SubtaskScoreConstraints
部分点120% (80 pts)$M \leq 10^9$
部分点230% (120 pts)$M \leq 10^{15}$
満点50% (200 pts)追加の制約は無い

Input

The input is given from standard input in the following format, where $case_i$ denotes the $i$-th case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$M$

Output

For each case, output -1 if no stage satisfying the conditions exists; otherwise, output one such stage in the following format. Here, $S_i\ (1 \leq i \leq N)$ is a string of length $N$, and the $j$-th character of $S_i$ must be . if the cell in the $i$-th row from the top and the $j$-th column from the left of the stage is a passage cell, # if it is a wall cell, and P if it is a switch cell.

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

Print a newline at the end of the output for each case.

Visualizer

A web version of the visualizer for output results is available here.

During the contest, sharing visualization results and mentioning solutions or analysis are prohibited. Please be careful.

In principle, we do not accept questions about the specifications of the visualizer. Please use it only as an auxiliary tool.

Sample

Sample 1
Input
1
3
Output
5
..P..
.#..#
.##.#
.P#..
...P.

There are $3$ paths that pass through a switch cell exactly $1$ time.

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