돌 게임

현재 돌 무더기들의 크기를 $x_1,x_2,\ldots,x_m$이라 하고, 현재까지 얻은 점수를 $S$라 하자. 다음 값을 생각한다.

$$P=S+\sum_{i=1}^{m}\frac{x_i(x_i-1)}{2}$$

크기가 $x$인 무더기를 크기 $a,b$인 두 무더기로 나누면 $x=a+b$이고 점수는 $ab$만큼 증가한다. 이때

$$\frac{a(a-1)}{2}+\frac{b(b-1)}{2}+ab=\frac{(a+b)(a+b-1)}{2}=\frac{x(x-1)}{2}$$

이므로 $P$는 연산 전후에 변하지 않는다.

처음에는 점수가 $0$이고 무더기가 하나뿐이므로 $P=\frac{N(N-1)}{2}$이다. 게임이 끝나면 모든 무더기의 크기가 $1$이므로 합의 각 항이 이 되고, 최종 점수는 반드시 가 된다.

따라서 만들 수 있는 최종 점수는 정확히 하나이며, $K=1$과 $\frac{N(N-1)}{2}$를 출력하면 된다. 계산 결과가 64비트 정수 범위를 넘을 수 있으므로 C++에서는 __int128과 같은 더 큰 정수형을 사용해야 한다.

시간 복잡도는 $O(1)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT5.6