No.5007 Steiner Space Travel
タグ : / 解いたユーザー数 118
作問者 : 👑
terry_u16
/ テスター :
butsurizuki
Note that the time limit is 1 second.
Story
Advances in astronomical observation technology have led to the discovery of many unknown planets. It has therefore been decided to survey all of these planets using a newly developed unmanned probe.
Traveling between planets consumes energy proportional to the square of the distance. Please place space stations serving as relay points at suitable locations and devise a survey route that consumes as little energy as possible.
Problem Statement
The coordinates of $N$ planets are given. Each planet lies on a two-dimensional plane, and the coordinates of the $i$-th planet are $(a_i, b_i)$.
There are also $M$ space stations, and the $j$-th space station can be placed at any integer coordinates $(c_j, d_j)$ satisfying $0 \le c_j \le 1000,\ 0 \le d_j \le 1000$.
Once a space station has been placed, it cannot be moved to different coordinates.
Planets and space stations are collectively called "waypoints". Let $V$ be the number of waypoints visited, and let $(x_k, y_k)$ be the coordinates of the $k$-th visited waypoint.
The energy $E_k\ (1\le k\le V-1)$ consumed when moving from the $k$-th waypoint to the $k+1$-th waypoint is defined as follows,
using the Euclidean distance between the waypoints $D_k=\sqrt{(x_k - x_{k+1})^2+(y_k - y_{k+1})^2}$ and a constant $\alpha\ (1\le \alpha)$.
- If the $k$-th waypoint and the $k+1$-th waypoint are both planets: $E_k=\alpha^2 D_k^2$
- If exactly one of the $k$-th waypoint and the $k+1$-th waypoint is a planet: $E_k=\alpha D_k^2$
- If the $k$-th waypoint and the $k+1$-th waypoint are both space stations: $E_k=D_k^2$
Note that in every case the energy consumed is proportional to the square of the Euclidean distance.
Place the space stations, and then find a route that starts from planet 1, visits every planet at least once, and returns to planet 1, such that the total energy consumed $\sum_{k=1}^{V-1} E_k$ is as small as possible.
The same waypoint may be visited any number of times, and some space stations may remain unvisited. The coordinates of a placed space station may also coincide with those of another waypoint.
Scoring
If the total energy consumed is $S$, you obtain $\mathrm{round}(10^9/(1000+\sqrt S))$ points.
However, an invalid output is judged as WA. An invalid output is any of the following.
- An output whose format is incorrect
- An output in which the value of a variable does not satisfy the constraints
- An output whose route does not start at planet 1
- An output whose route does not end at planet 1
- An output in which an unvisited planet exists
There are 30 test cases in total, and the score of a submission is the sum of the scores over all test cases.
The final ranking is determined by the highest score obtained during the contest, and no system test is performed after the contest ends.
Input
In all test cases, $α=5$ is fixed.
Input is given from Standard Input in the following format.
$N\ M$ $a_1\ b_1$ $\vdots$ $a_N\ b_N$
Each variable satisfies the following constraints.
- $N=100$
- $M=8$
- $0\le a_i\le 1000$
- $0\le b_i\le 1000$
- If $i\ne i'$, then $(a_i, b_i)\ne(a_{i'}, b_{i'})$
- All input values are integers
Output
Print to Standard Output in the following format, ending with a newline.
$c_1\ d_1$ $\vdots$ $c_M\ d_M$ $V$ $t_1\ r_1$ $\vdots$ $t_V\ r_V$
Here, $t_k$ is an integer representing the type of the $k$-th waypoint: 1 for a planet and 2 for a space station.
Also, $r_k$ is the number of the $k$-th waypoint, with $1\le r_k\le N$ for a planet and $1\le r_k\le M$ for a space station.
Each variable must satisfy the following constraints.
- $0\le c_j\le 1000$
- $0\le d_j\le 1000$
- $1\le V\le 10^5$
- $t_k\in \{ 1, 2 \}$
- If $t_k=1$, then $1\le r_k\le N$
- If $t_k=2$, then $1\le r_k\le M$
- $t_1 = t_V = 1$
- $r_1 = r_V = 1$
- All output values are integers
Input Generation
This section is not essential for understanding the problem.
The input is generated by the following procedure. Here, $\mathrm{rand}(L, U)$ denotes a function that generates an integer uniformly at random between $L$ and $U$, inclusive.
- For $l=1,2,\cdots,15$, generate a reference point $(u_l, v_l)$ by the following procedure.
- Let $u_l=\mathrm{rand}(100, 900),\ v_l=\mathrm{rand}(100, 900)$.
However, if any already generated reference point has a Euclidean distance of 100 or less from $(u_l, v_l)$, regenerate $u_l,\ v_l$.
- Let $u_l=\mathrm{rand}(100, 900),\ v_l=\mathrm{rand}(100, 900)$.
- For $i=1,2,\cdots,N$, generate the coordinates $(x_i, y_i)$ of the $i$-th planet by the following procedure.
- Generate $m_i=\mathrm{rand}(1, 15)$.
- Let $\Delta x_i=\mathrm{rand}(-100, 100),\ \Delta y_i=\mathrm{rand}(-100, 100)$, and let $x_i=u_{m_i}+\Delta x_i,\ y_i=v_{m_i}+\Delta y_i$.
However, if $(x_i, y_i)$ coincides with the coordinates of an already generated planet, regenerate $m_i,\ \Delta x_i,\ \Delta y_i$.
Tools (Input Generator and Visualizer)
- Web version
- It has the following features.
- Test case generation
- Score calculation and visualization
- Image sharing to Twitter
- During the contest, sharing images on Twitter is permitted only for the results of seed=0. List of shared images
- Shared images may contain minor spoilers. If you wish to avoid spoilers completely, please mute
#SteinerSpaceTravelon your own.
- It has the following features.
- Local version
- It has the following features.
- Test case generation
- Score calculation and visualization
- Parallel execution and aggregation of multiple cases
- Using it requires .NET Runtime 6. See the included
README.md.
- It has the following features.
Sample
Sample 1
Input
2 1 0 0 200 200
Output
200 0 4 1 1 1 2 2 1 1 1
This case does not satisfy the constraints $N=100,\ M=8$, so it is never given as an actual test case.
This case is illustrated in the figure below.
The large blue circle represents planet 1, the yellow circles represent the other planets, and the gray squares represent space stations.
Initially, planet 1 is at $(0, 0)$ and planet 2 is at $(200, 200)$.
Space station 1 is placed at $(200, 0)$, and the waypoints are visited in the order planet 1 → planet 2 → space station 1 → planet 1.
The energy required for each move is as follows.
- Planet 1 → planet 2: $5^2\times(200^2+200^2)=2\times10^6$
- Planet 2 → space station 1: $5\times(0^2+200^2)=2\times10^5$
- Space station 1 → planet 1: $5\times(200^2+0^2)=2\times10^5$
The score in this case is $\mathrm{round}(10^9/(10^3+\sqrt{2\times10^6+2\times10^5+2\times10^5}))=329981$ points.
Sample 2
Input
3 4 100 100 0 0 0 100
Output
150 150 100 100 150 150 100 200 8 1 1 2 4 2 4 1 3 1 2 1 3 2 2 1 1
This case does not satisfy the constraints $N=100,\ M=8$, so it is never given as an actual test case.
This case is illustrated in the figure below.
None of the following conditions makes an output invalid.
- Placing a space station at the same coordinates as a planet
- Placing multiple space stations at the same coordinates
- Waypoint $k$ and waypoint $k+1$ being identical
- Visiting the same waypoint multiple times
- Having a space station that is not visited
Therefore, this output is valid, and it scores $544467$ points.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。