No.3743 World Mapper
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.
| Subtask | Score | Constraints |
|---|---|---|
| 部分点1 | 10% (50 pts) | $N \leq 5$ |
| 部分点2 | 10% (50 pts) | $N \leq 10$ |
| 部分点3 | 10% (50 pts) | $N \leq 15$ |
| 部分点4 | 10% (50 pts) | $N \leq 20$ |
| 部分点5 | 10% (50 pts) | $N \leq 25$ |
| 部分点6 | 10% (50 pts) | $N \leq 30$ |
| 部分点7 | 10% (50 pts) | $N \leq 35$ |
| 部分点8 | 10% (50 pts) | $N \leq 40$ |
| 部分点9 | 10% (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もしくは右上の雲マークをクリックしてアカウントを作成してください。