버거 최적화

2017년, Google은 심각한 안드로이드 버그를 알게 되었다. 버거 이모지에서 치즈가 패티 위가 아니라 아래쪽 번 바로 위에 놓여 있었던 것이다. 정말이지, 누가 버거를 그렇게 만드는가? 우리 CEO 순다르는 당장 모든 일을 제쳐 두고 이 문제를 해결하겠다고 다짐했다.

이런 일이 다시는 일어나지 않도록, Code Jam 팀은 버거를 이해하기 위한 수학적 모델을 만들었다. 버거는 두 개의 번 사이에 K개의 재료가 쌓인 형태이며, 각 재료는 정확히 한 번씩 등장한다. 우리는 각 재료의 번까지의 거리 값에 관심이 있다. 어떤 재료의 번까지의 거리 값은 그 재료와 번 사이에 있는 다른 재료의 최소 개수이다.

• K가 짝수이면, 재료들의 번까지의 거리 값은 (쌓인 순서의 맨 위 재료부터 시작해서) 0, 1, ..., K/2 - 1, K/2 - 1, ..., 1, 0이다.
• K가 홀수이면, 0, 1, ..., ((K - 1) / 2) - 1, (K - 1) / 2, ((K - 1) / 2) - 1, ..., 1, 0이다.

많은 포커스 그룹 테스트를 거치고 (그리고 버거를 많이 먹고) 나서, 우리는 K개의 재료 중 i번째 재료의 최적 번까지의 거리 값이 Di라는 것을 알아냈다. 우리는 각 재료의 최적 거리 값과 실제 거리 값의 차이의 제곱의 합으로 정의되는 오차 값을 최소화하는 재료 순서를 선택할 때 버거 이모지 사용자들이 가장 행복해할 것이라고 생각한다.

예를 들어, 최적 번까지의 거리 값이 각각 0, 2, 1, 1, 2인 다섯 개의 재료 A, B, C, D, E가 있고 이들을 그 순서대로 번 사이에 놓으면, 오차는 (0-0)2 + (2-1)2 + (1-2)2 + (1-1)2 + (2-0)2 = 6이다. 대신 C, E, B, D, A 순서로 놓으면 오차는 (1-0)2 + (2-1)2 + (2-2)2 + (1-1)2 + (0-0)2 = 2이며, 이 값이 이 재료들에서 가능한 최소 오차이다.

재료들의 최적 번까지의 거리 값 목록이 주어졌을 때, 가능한 최소 오차를 구할 수 있는가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 버거의 재료 수 K를 담은 한 줄로 시작한다. 그다음 줄에는 K개의 정수 Di, 즉 재료들의 최적 번까지의 거리 값이 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 가능한 최소 오차이다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 0 ≤ Di ≤ floor((K-1)/2). (각 최적 번까지의 거리 값은 달성 가능한 번까지의 거리 값의 범위 안에 있다.)

예제 1은 문제 지문에서 설명한 경우이다.

예제 2에서는 버거에 재료가 하나뿐이다. 버거라고 하기엔 좀 그렇지만, 우리 모델은 이런 기본적인 경우도 처리할 수 있어야 한다! 재료 하나를 어떻게 놓을지에 대한 혼란은 없으며, 오차는 0이다.

예제 3에서는 재료가 여섯 개이지만 모두 최적 번까지의 거리가 2이다. 어떻게 놓든 결과는 같으며, 오차는 22 + 12 + 02 + 02 + 12 + 22 = 10이다.