25300번 - 방송국 서브태스크언어 제한함수 구현

$N$개의 방송국들, $s_1, s_2, \dots, s_N$이 직선 위에 위치한다. 방송국 $s_i$의 위치는 양의 정수 $x_i$로 주어지고, 여러분은 각각의 방송국 $s_i$에 대해 방송 전파의 범위 $r_i$를 할당해야 한다. 방송국 $s_i$가 방송을 하면 $s_i$로부터 거리 $r_i$안의 방송국들은 $s_i$의 방송 전파를 받을 수 있다. 다시 말해서, 방송국 $s_j$가 닫힌구간 $[x_i-r_i,x_i+r_i]$안에 위치하면 $s_j$는 $s_i$의 방송 전파를 받을 수 있다.

방송국 $s_i$의 방송은 $h-1$ ($h > 1$)개의 방송국들이 이어 전달해서 방송국 $s_j$에 전달 될 수 있다. 다시 말해서, 방송국 $s_{i_1}, s_{i_2}, \dots, s_{i_{h-1}}$이 존재해서, $s_i$의 방송을 $s_{i_1}$에 전달하고, 각 $s_{i_k}$가 $s_{i_{k+1}}$로 전달하고, $s_{i_{h-1}}$이 $s_j$에 전달해서 $h$번 만에 $s_i$의 방송이 $s_j$에 전달될 수 있다. 물론 $h=1$인 경우 는 $s_i$의 방송이 직접 $s_j$에 전달되는 경우이다. 이런 경우들에 대해 $s_i$의 방송이 $h$-단계에 $s_j$에 전달된다고 말한다.

우리는 방송국들 중에 하나의 방송국을 정하고 싶다. 이 방송국은 방송하지 않고 단지 다른 모든 방송국들로부터 많아야 $h$-단계 만에 그들의 방송을 받아야 한다. 이 방송국을 $h$-집중국 이라고 한다. $h$-집중국의 방송 전파 범위는 $0$이라 할 수 있다.

각 방송국 $s_i$에 전파 범위 $r_i$를 할당할 때, 할당 비용을 전파 범위의 제곱의 합으로 정의한다. 다시 말해서 비용은 $\displaystyle\sum_{i=1}^{N}{r_i^2}$로 주어진다. 우리는 이 비용이 최소가 되도록 전파 범위들을 할당할 것이다. 방송국 $s$가 $h$-집중국인 경우에 최소 할당 비용을 $C_h^*(s)$로 나타내면, 문제의 목표는 모든 가능한 $h$-집중국 $s$의 최소 할당 비용 $C_h^*(s)$들 중 최솟값을 가지는 $h$-집중국과 그 최소비용을 주는 전파 범위 할당을 찾는 것이다.

$N$개 방송국들의 위치가 주어질 때, 각 $h=1, 2, \dots, N-1$에 대해서, 모든 가능한 $h$-집중국 $s$의 최소 할당 비용 $C_h^*(s)$의 최솟값을 출력하는 프로그램을 작성하시오.

예를 들어, 아래 그림 1과 2는 $5$개의 방송국 $s_1, \dots, s_5$가 각각 좌표 $1, 3, 4, 6, 9$에 위치하고 $h=2$인 경우이다. 이 때, 그림 1처럼 $s_1, s_2, s_3, s_4$에 각각 $3, 1, 5, 2$의 전파 범위를 할당할 때 $s_5$가 $h$-집중국인 경우의 최소 비용 $39$를 가진다. 그림 2처럼 $s_1, s_2, s_4, s_5$에 각각 $2, 1, 2, 3$의 전파 범위를 할당할 때 $s_3$이 $h$-집중국인 경우의 최소 비용 $18$을 가진다. 그러면 $18$이 모든 가능한 $h$-집중국들에 대한 최소 비용들 중 최솟값이다.

그림 1

그림 2

여러분은 관리자를 위해 다음 한 가지 함수를 구현해야만 한다.

• void stations(int N, int X[]) ; 방송국들의 개수 $N$, 각 방송국의 위치를 나타내는 $X[0..N-1]$를 인자로 받는다. 여기서, $X[]$는 크기 $N$인 벡터(vector)이고, $X[i]$의 값은 모두 다르고 오름차순으로 저장되어 있다.

여러분은 stations() 함수 안에서 다음 함수를 사용하여 답을 제출하여야 한다.

• void answer(long long Y[]) : 크기 $N-1$인 벡터 $Y[]$를 제출하는 함수이다. $i=0,\dots, N-2$에 대해서, $Y[i]$의 값은 모든 가능한 $(i+1)$-집중국들의 최소비용의 최솟 값이다. 이 함수는 stations() 함수 안에서 정확히 한 번 호출되어야 한다.

여러분은 stations.cpp라는 이름의 정확히 하나의 파일을 제출해야만 한다. 이 파일에는 다음의 함수가 구현되어야 한다.

void stations(int N, int X[]);

이 함수는 위에서 설명한 것과 같이 동작하여야 한다. 물론, 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안된다.

주어지는 그레이더는 다음과 같은 형식으로 입력을 읽는다:

• line $1$: $N$ ($N$: 방송국들의 개수)
• line $2$: $N$개의 정수 $x_1$ $x_2$ $\cdots$ $x_N$ ($x_i$: 방송국의 위치)

주어지는 그레이더는 각 $i=1, \dots, N-1$에 대해서, $i$번째 줄에 모든 가능한 $i$-집중국들의 최소비용의 최솟값을 출력한다.

• $2 \le N \le 120$
• $1 \le x_1 < x_2 < \cdots < x_N \le 10^8$