問題一覧 > 通常問題

No.3743 World Mapper

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

Story

The travel distance from Sapporo to Abashiri and the travel distance from Osaka to Hiroshima are almost the same (opinions vary).

By the way, kencho-kun now wants to go for a drive on a grid graph. He decided that every day, after choosing the distance he wants to drive, he would look for a pair of start and end points satisfying the condition and drive there, but he realized that if multiple such pairs exist, he would be unsure where to drive. Note that kencho-kun uses a car navigation system, so he always drives along a shortest path.

Let's build a grid graph that saves kencho-kun from this indecision.

Problem Statement

There is an undirected grid graph $G$ with vertices arranged in $N$ rows and $N$ columns. For $1 \leq i, j \leq N$, the vertex in the $i$-th row from the top and the $j$-th column from the left of $G$ is numbered $(i - 1) N + j$.

For each edge of $G$, you may choose an integer between $1$ and $3 \times 10^5$, inclusive, as its weight.

The length of a path is the sum of the weights of the edges it contains. The shortest distance between $2$ vertices is the minimum length of a path connecting those $2$ vertices.

There are $\frac{N^2(N^2-1)}{2}$ unordered pairs of $2$ distinct vertices. Determine the weight of each edge so that the shortest distances between the $2$ vertices of these pairs are all different.

More formally, letting $d_{i,j}$ be the shortest distance between vertices $i$ and $j$ of $G$ for $1 \leq i \lt j \leq N^2$, make it so that $(i_1, j_1) \neq (i_2, j_2) \Rightarrow d_{i_1,j_1} \neq d_{i_2,j_2}$ holds.

It is allowed for multiple shortest paths to connect the same $2$ vertices.

If no assignment of edge weights satisfies the condition, output -1.

Constraints

  • All inputs are integers.
  • $2 \leq N \leq 50$

Partial Score

This problem has partial scoring based on subtasks.

SubtaskScoreConstraints
部分点110% (50 pts)$N \leq 5$
部分点210% (50 pts)$N \leq 10$
部分点310% (50 pts)$N \leq 15$
部分点410% (50 pts)$N \leq 20$
部分点510% (50 pts)$N \leq 25$
部分点610% (50 pts)$N \leq 30$
部分点710% (50 pts)$N \leq 35$
部分点810% (50 pts)$N \leq 40$
部分点910% (50 pts)$N \leq 45$
満点10% (50 pts)追加の制約は無い

Input

The input is given from standard input in the following format.

$N$

Output

Output the weight of each edge in the following format. Here, $v_{i, j}$ denotes the weight of the vertical edge connecting vertex $(i-1)N + j$ and vertex $iN + j$, and $h_{i, j}$ denotes the weight of the horizontal edge connecting vertex $(i-1)N + j$ and vertex $(i-1)N + j + 1$.

$v_{1,1}\ v_{1,2}\ \ldots\ v_{1,N}$
$v_{2,1}\ v_{2,2}\ \ldots\ v_{2,N}$
$\vdots$
$v_{N-1,1}\ v_{N-1,2}\ \ldots\ v_{N-1,N}$
$h_{1,1}\ h_{1,2}\ \ldots\ h_{1,N-1}$
$h_{2,1}\ h_{2,2}\ \ldots\ h_{2,N-1}$
$\vdots$
$h_{N,1}\ h_{N,2}\ \ldots\ h_{N,N-1}$

If no assignment of edge weights satisfies the condition, output -1.

Print a newline at the end.

Visualizer

A web-based visualizer for the output is available here.

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

In principle, questions about the visualizer's specifications will not be accepted. Please use it only as an auxiliary tool.

Sample

Sample 1
Input
2
Output
1 3
6
4

The shortest distances between each pair of vertices are as follows, and they are all different.

  • The shortest distance between vertices $1$ and $2$ is $6$
  • The shortest distance between vertices $1$ and $3$ is $1$
  • The shortest distance between vertices $1$ and $4$ is $5$
  • The shortest distance between vertices $2$ and $3$ is $7$
  • The shortest distance between vertices $2$ and $4$ is $3$
  • The shortest distance between vertices $3$ and $4$ is $4$

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