시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4.814 초 | 814 MB | 1074 | 0 | 0 | 0.000% |
최근 불어온 TSP(Traveling Salesman Problem)의 열기에 힘입어 다음과 같은 문제를 만들었다:
2차원 평면 위에 $N$개의 도시가 있다. $i$번째 도시의 좌표는 ($x_i$, $y_i$)로 나타난다.
회사는 $N$개의 도시를 $K$명의 외판원에게 분배한다. $k$번째 외판원이 받은 도시의 개수를 $c_k$라고 하자.
각 외판원은 받은 도시를 순회할 순서 $p_{k,1}$, $p_{k,2}$, $\cdots$, $p_{k,c_k}$를 정하여, $p_{k,1}$부터 순서대로 모든 도시를 돌고 다시 $p_{k,1}$로 되돌아온다. 이때, 각 외판원이 이동하는 거리의 최댓값을 최소화하라.
$i$번 도시와 $j$번 도시 사이의 거리 $d(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$이며, 문제는 결국 $\max_{k=1}^{K} {\sum_{j=1} ^{c_k} d(p_{k,j}, p_{k,j+1})}$를 최소화하는 것이다. 편의상, $p_{k,c_k+1}=p_{k,1}$이다.
첫 번째 줄에 도시의 개수 $N=8 \; 000$과 외판원의 수 $K=140$가 주어진다.
다음 $N$개의 줄의 $i$번째 줄에는 $i$번 도시의 좌표를 나타내는 두 정수 $x_i, y_i$ ($0 \leq x_i, y_i \leq 814 \; 000$)가 주어진다.
주어지는 $x_i, y_i$는 주어진 범위 내의 정수 중 하나를 모두 동일한 확률로 선택하여 만들어졌다.
채점에는 총 50개의 입력이 사용되며, 총점은 각 점수의 합이다.
$K$개의 줄에 걸쳐 답을 출력해야 하며, $k$번째 줄에는 $c_k$, $p_{k,1}$, $p_{k,2}$, $\cdots$, $p_{k,c_k}$가 순서대로 출력되어야 한다.
출력에서 모든 외판원은 적어도 하나의 도시를 분배받아야 하고, 모든 도시는 정확히 한 번씩 등장해야 한다.
3 2 0 0 3 0 3 1
2 3 2 1 1
예제는 $N=3$, $K=2$로 주어졌지만, 채점에서 사용되는 모든 입력은 $N= 8 \; 000$, $K=140$이다.