Acperience

심층 신경망(DNN)은 컴퓨터 비전과 음성 인식을 비롯한 여러 응용 분야에서 큰 성능 향상을 보여 왔다. 컴퓨터 비전에서는 합성곱 신경망(CNN)이라는 특정한 종류의 DNN이 객체 인식과 검출에서 최고 수준의 결과를 냈다.

합성곱 신경망은 실제 응용에 쓸모 있는 객체 인식과 검출에서 신뢰할 만한 결과를 낸다. 인식 분야의 최근 발전과 더불어 가상 현실(Oculus의 VR), 증강 현실(HoloLens의 AR), 스마트 웨어러블 기기에서도 흥미로운 진전이 있었다. 이 두 가지를 합치면, 최신 인식 시스템의 성능을 스마트 휴대 기기에 탑재할 적기라고 할 수 있다. 그러나 CNN 기반 인식 시스템은 많은 메모리와 연산 능력을 필요로 한다. 값비싼 GPU 기반 기계에서는 잘 동작하지만, 휴대폰이나 임베디드 전자 기기처럼 작은 장치에는 대개 적합하지 않다.

네트워크를 단순화하기 위해 장(張) 교수는 가중치를 이진화하여 CNN에 단순하고 효율적이며 정확한 근사를 도입하려 한다. 장 교수는 여러분의 도움이 필요하다.

더 구체적으로, 가중치 벡터 $W = (w_1, w_2, \ldots, w_n)$가 주어진다. 장 교수는 이진 벡터 $B = (b_1, b_2, \ldots, b_n)$ ($b_i \in \{-1, +1\}$)와 실수 스케일 인자 $\alpha \ge 0$를 골라 $\left\|W - \alpha B\right\|^{2}$가 최소가 되게 하려 한다.

여기서 $\left\|\cdot\right\|$는 유클리드 노름을 나타낸다. 즉, $X = (x_1, x_2, \ldots, x_n)$일 때 $\left\|X\right\| = \sqrt{x_{1}^{2} + \cdots + x_{n}^{2}}$이다.

여러 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 정수 $n$ ($1 \le n \le 100\,000$)이 주어진다. 이는 주어진 가중치 벡터의 길이이다. 다음 줄에는 $n$개의 정수 $w_1, w_2, \ldots, w_n$ ($-10\,000 \le w_i \le 10\,000$)이 주어진다.

테스트 케이스는 $400$개를 넘지 않는다. 입력의 총 크기는 $7$ 메비바이트 이하이다.

각 테스트 케이스마다 $\left\|W - \alpha B\right\|^2$의 최솟값을 기약분수 $p$/$q$로 출력한다. 여기서 $p$와 $q$는 정수이고 $q > 0$이다.