제3회 고려대학교 MatKor Cup : 2023 Summer Open Contest - Phase 1

문제의 설명과 같이 각 평행세계별로 처음 출력한 과목과 다른 과목 중 입력으로 주어지지 않은 과목을 출력하면 됩니다.

인터랙티브 문제이므로, 각 줄에 대해 개행을 하고 `flush`를 해 주어야 합니다.

주어진 $n$이 제곱수라면,

- $\sqrt{n}$은 정수입니다.
- 임의의 정수 $a$에 대해 $(\sqrt{n}, a, \sqrt{n+a^2})$이 직각삼각형을 이룹니다.
- $\sqrt{n}$과 $a$가 정수이므로, 조건을 만족하는 직각삼각형은 무수히 많습니다.
 
주어진 $n$이 제곱수가 아니라면,

- $\sqrt{n}$은 정수가 아니므로, 나머지 두 변이 정수 $a, b$($a\le b$)여야 합니다.
- $\sqrt{n}$이 빗변이라면,
  - 피타고라스 정리에 의해 $a^2+b^2=n$이 성립합니다.
  - $1\le a\le \sqrt{\frac{n}{2}}<10^6$이므로 해당 범위의 모든 수들에 대해 $n-a^2$이 제곱수인지 검사하면 됩니다.
- $\sqrt{n}$이 빗변이 아니라면,
  - 피타고라스 정리에 의해 $a^2+n=b^2$이 성립합니다.
  - $n=b^2-a^2=(b+a)(b-a)$이므로, $n$을 홀짝성이 같은 서로 다른 두 수의 곱으로 분리하면 됩니다.
  -  $b+a > b-a$이므로 $1\le b-a < \sqrt{n}\le 10^6$이고, 해당 범위의 모든 수들에 대해 $n$의 약수이며, $n$을 그 수로 나눈 값과 홀짝성이 같은지 확인해주면 됩니다.


제곱수인지 판단하는 시간복잡도는, $\sqrt{n}$까지를 제곱한 수를 $\mathcal{O}\left(\sqrt{n}\right)$에 모두 저장한 뒤 이분탐색 혹은 집합을 통해 쿼리당 $\mathcal{O}\left(\log n\right)$에 계산하는 방식을 의도하였습니다.

위의 방법 외에도 `sqrt` 함수를 이용해 비교해도 범위 내에서 오차가 발생하지 않습니다.

즉, $\mathcal{O}\left(\sqrt{n}\right)$개의 쿼리를 비교해야 하므로 $\mathcal{O}\left(\sqrt{n} \log n\right)$에 해결 가능합니다.

날짜가 지날수록 실제 전일 대비 성장 값이 단조감소해야 합니다. 이를 다르게 생각하면, $x$축을 날짜 축, $y$축을 실제 키 축으로 두어 점을 찍어 사이를 선분으로 그릴 때, $x$좌표가 커지면 기울기가 작아지거나 유지되면 됩니다.

$i$번째 날에 유림이가 공책에 쓴 값이 $a_i$라고 하면, 실제 가능한 구간은 $[a_i-0.5,a_i+0.5)$입니다.

여기서 그래프를 평행 이동해도 답에는 변화가 없으므로, 처음 구간을 $x=0$, $y\in[0,1)$로 둡니다. 그러면 입력되는 값이 $a_1, a_2, \cdots a_n$이라 하고, $S_i=\sum_{j=1}^ia_i$라 하면, $x=i$일때 구간은 $y\in[S_i,S_i+1)$입니다.

즉, 입력으로 `3 1 0 0 1`이 들어오면 첫 번째 그림, `3 1 0 0 1 1`이 들어오면 두 번째 그림입니다.

![입력이 3 1 0 0 1인 경우](https://static.solved.ac/arena/editorial/3/gs1-1.png)
![입력이 3 1 0 0 1 1인 경우](https://static.solved.ac/arena/editorial/3/gs1-2.png)


결론적으로 문제는 여기서 모든 선분을 통과하는 오목함수를 찾는 것으로 바뀝니다. 이는 선분의 아래 점들로 이루어진 monotone chain(볼록 껍질의 절반)을 찾는 것과 같습니다.

물론 볼록 껍질 알고리즘을 바로 적용해도 되나, $x$-좌표가 증가하는 방향으로 되어 있고, $x$가 증가함에 따라 $y$도 단조증가하므로, 답을 다양한 방식을 통해 구할 수 있습니다.

- $x$를 증가시키며 스택에 점을 삽입하며 단조 감소를 유지시키는 방식(LIS 혹은 히스토그램 문제와 유사하지만 점의 기울기의 업데이트가 필요함)으로 답을 구할 수 있습니다.
- 혹은 아래의 점에 볼록 껍질 알고리즘을 적용시켜 구할 수 있습니다.

출제자는 monotone chain에서 한쪽 껍질만 구하는 방식으로 정해 코드를 작성하였습니다. 즉, 볼록 껍질보다 쉬운, 그에 포함되는 방식으로 구할 수 있습니다.

![입력이 3 1 0 0 1인 경우](https://static.solved.ac/arena/editorial/3/gs1-3.png)
![입력이 3 1 0 0 1 1인 경우](https://static.solved.ac/arena/editorial/3/gs1-4.png)

이렇게 monotone chain을 만들었다면, 그 monotone chain이 기존 $N+1$개의 선분 구간을 지나는 지 확인해 줍니다. 이는 직선의 방정식 혹은 선분 교차 판정 등의 방법으로 확인할 수 있습니다. 이때, $N+1$개의 선분 구간의 아래점은 포함되지만, 위의 점은 아니라는 것을 주의해야 합니다.

만약 모든 선분 구간과의 교점이 생기면, 해당 monotone chain이 예시 이므로 `Not Provable`, 교점이 안 생기는 선분 구간이 존재하면 `Provable`을 출력합니다. 세 번째 그림은 모든 구간 교점이 생기지만, 네 번째 그림은 $x=4$일때 상한은 지나지만 교점이 생기지 않습니다.

Monotone chain 등의 방식을 통해 구하는 과정에서 $\mathcal{O}\left(N\right)$이 소요되며, 교차 판정도 $\mathcal{O}\left(N\right)$이 소요됩니다.


$1$번부터 $9$번 프레임까지를 **일반 프레임**, $10$번 프레임을 **마지막 프레임**이라고 부릅시다. 먼저, $A$에 `?`가 없을 때 가능한 모든 경우를 저장합니다. 해당하는 경우는 다음과 같습니다.

- $1\le i \le 9$에 대해:
  - $1\le j\le 9-i$에 대해 $(i,j)$
  - $(i, \texttt{/})$
  - $(i, \texttt{-})$
  - $(\texttt{-}, i)$
- $(\texttt{X}, \texttt{.})$
- $(\texttt{-}, \texttt{/-})$
- $(\texttt{-}, \texttt{/})$

총 $\lvert A\rvert =36+9+9+9+3=66$가지의 경우가 가능합니다.

점수의 최댓값 $S$는, 프레임 수가 $n$이라고 하면,
- $1$번부터 $n-2$번 프레임 보너스 포함 최대 $20$점
- $n-1$번 프레임 보너스 포함 최대 $30$점
- $n$번 프레임 최대 $30$점
이므로, $S=20n+20$이 성립합니다. 이 문제에서는 $n=10$, $S=220$이다.

이제 $\mathit{dp}[i][j][k]$를 $i\in [1,n]$, $j\in A$, $k \in [0, S]$에서 다음과 같이 정의합시다.

$$
\begin{aligned}
\mathit{dp}[i][j][k] =\ & i\text{번째 프레임에서 투구가 }j\text{였을 때,} \\ & \text{뒤에서부터 고려하여 마지막 프레임부터 } \\ & i\text{번 프레임까지 얻은 점수의 합이 }k\text{인 경우의 수}
\end{aligned}
$$

이때 $n$번 프레임의 경우 따로 처리해 주며, 이때의 점수와 함께 $9$번에서 스페어 혹은 스트라이크를 쳤을 때 더해지는 보너스 점수를 각각 변수로 만들어 저장합니다.

그러면 $i$를 $n-1$부터 $1$까지
- $j\in A$, $k\in A$, $l \in [0,S]$에 대해, $j$가 주어진 정보에서 `?`를 제외하고 일치할 때(즉, `??`는 모두 일치합니다),
  $$
  \mathit{dp}[i][j][l]=\displaystyle\sum \mathit{dp}[i+1][k][l-\mathit{score}(j)-\mathit{bonus}(j,k)]
  $$
- 이때, $n$번 프레임에 대한 $k$는 $A$만 있지 않을 수 있으므로, $n-1$번 프레임은 따로 처리합니다.

위의 과정을 통해 계산하면 $p[M]=\displaystyle\sum_{y \in A}\mathit{dp}[1][y][M]$이 최종적으로 $M$점을 얻는 경우의 수입니다. 즉, $\mathcal{O}\left({\lvert A\rvert^2 nS + \lvert A\rvert}\right)\equiv\mathcal{O}\left({\lvert A\rvert^2 nS}\right)$에 모든 점수에 대한 답을 구할 수 있습니다.

따로 $A$를 저장할 배열이나 집합을 만들지 않고 구현하는 경우, `?.`의 경우 `?`는 `X`만 가능하며, `?-`의 경우 `?`에는 `X`가 불가능합니다. 이외에도 $37$이 불가능한 등 다양한 예외처리를 해야 하므로 $A$를 만들어 관리하는 편이 문제해결에 용이합니다.

우선 $N$과 $M$이 작을 때부터 생각해 봅시다.
- 먼저 $N = 1$ 또는 $M = 1$인 경우, 선공이 첫 블록을 놓자마자 승리 조건이 달성되므로 선공을 골라야 합니다.
- 다음으로 $N = 2$ 또는 $M = 2$인 경우, 선공이 첫 블록을 놓게 되면 후공이 선공의 승리를 막기 위해 같은 행 또는 열에(칸이 2개인 곳에) 놓아야 합니다. 이 과정이 반복되면 결국 선공의 승리 조건이 달성되므로 이 때에도 선공을 골라야 합니다.

이외의 경우를 나눠 생각해 봅시다.

### (홀수) $\times$ (홀수)의 경우

이 경우, 선공에게 다음과 같은 전략이 존재합니다.
- 처음에는 아무 곳에나 둡니다.
- 이후, 상대가 $1$행에 놓으면 남은 $1$행의 위치 중 아무 곳에나 둡니다. 남은 $1$행의 개수가 짝수이므로 항상 놓을 수 있습니다.
- 만약 상대가 $1$행이 아닌 곳에 놓으면 반드시 그 위에 놓습니다.
- 이를 반복하면 $3$행이 모두 파란색이 되므로 선공이 승리합니다.

### (홀수) $\times$ (짝수)의 경우

이 때에는 선공이 (홀수) $\times$ (홀수)에서의 전략을 사용할 수 없습니다. 선공이 이전 전략을 사용한다고 했을 때, 후공이 한 행을 모두 채우게 되면 선공이 반드시 짝수 행에 놓아야 하는 경우가 생기기 때문입니다.

이 경우에는 후공에게 다음과 같은 전략이 존재합니다.
- 선공이 처음 둔 열을 $A$라고 하고, 그 다음 $A$가 아닌 임의의 열 $B$에 후공이 둡니다.
- 이후, 상대가 $A$ 혹은 $B$에 놓으면 그 위에 둡니다. 만약 그 위에 둘 수 없다면 $A$와 $B$ 중 다른 열에 둡니다.
- 만약 상대가 $A$와 $B$가 아닌 열에 놓는다면 그 위에 둡니다. 높이가 짝수이므로 항상 놓을 수 있습니다.

이 전략이 가능한 이유는 다음과 같습니다.
- 우선, 모든 열과 첫 행이 막혔다는 사실은 자명합니다.
- $A$와 $B$ 중 먼저 채워진 열에 의해 $3$행 이상의 홀수 행이 모두 막힙니다.
- 이외의 열들에 의해 $2$행 이상의 짝수 행이 모두 막힙니다.
- 모든 행과 열이 막혔으므로 후공이 승리합니다.

### (짝수) $\times$ (홀수)

이 경우에는 후공에게 다음과 같은 전략이 존재합니다.
- 열의 개수가 짝수이므로 두 열씩 짝을 짓습니다. $X$열과 $Y$열이 짝지어졌다면, $f(X)=Y$, $f(Y)=X$라고 합시다.
- 처음에 상대가 둔 열이 $A$일 때, $B=f(A)$에 놓습니다.
- 이후, 상대가 $A$ 혹은 $B$에 놓으면 그 위에 둡니다. 남은 높이가 짝수이므로 항상 놓을 수 있습니다.
- 만약 상대가 $A$와 $B$가 아닌 열에 놓는다면 그 위에 둡니다. 만약 그 위에 둘 수 없다면 짝이 지어진 다른 열 위에 놓습니다. 즉, 상대가 놓은 열이 $K$일 때 $f(K)$에 놓습니다.

이 전략이 가능한 이유는 다음과 같습니다.
- 우선, 모든 열과 첫 행이 막혔다는 사실은 자명합니다.
- $A$와 $B$에 의해 3행 이상의 홀수 행이 모두 막힙니다.
- 이외의 열들에 대해 $K$와 $f(K)$ 중 먼저 채워진 열에 의해 2행 이상의 짝수 행이 모두 막힙니다.
- 모든 행과 열이 막혔으므로 후공이 승리합니다.

### (짝수) $\times$ (짝수)

(홀수) $\times$ (짝수)의 경우와 같은 전략이 후공에게 존재합니다.
- 열의 개수가 짝수인 경우, 후공의 전략으로 선공이 놓는 곳에 항상 대칭되는 곳에 놓는 전략은 다음과 같은 반례가 존재하기 때문에 적절한 전략이 아닙니다.
- $4 \times 4$의 상황을 가정합니다. 아래와 같은 상황에서는 선공의 승리를 막을 수 없습니다.
- $(1, 1)$(선공) &rarr; $(4, 1)$(후공) &rarr; $(1, 2)$(선공) &rarr; $(4, 2)$(후공) &rarr; $(1, 3)$(선공) &rarr; $(4, 3)$(후공) &rarr; (1, 4)(선공)

따라서, 각 테스트케이스마다 $\mathcal{O}\left(1\right)$의 시간복잡도로 선공과 후공 중 어떤 것을 골라야하는지 판단 가능합니다. 총 $\mathcal{O}\left(T\right)$의 시간복잡도로 전체 문제를 해결할 수 있습니다.


## 풀이 1

풀이 1은 〈감소하는 성장률의 비극 1〉을 해결했다고 생각합니다.

〈감소하는 성장률의 비극 1〉의 경우 단조 감소하는 직선 중 어느 것을 찾아도 되지만, 이번에는 그 중 직선, 그 중에서도 기울기가 가장 큰 것을 찾아야 한다. 기존에 아래 점들에 대한 monotone chain을 찾았다면, 위쪽 점들에 대한 볼록함수인 monotone chain을 찾으면 됩니다.

아래는 입력이 `0 1 0 0 1`인 경우입니다.
- 아래의 빨간색, 초록색과 같이 monotone chain을 그렸다면, 그 사이를 지나는 최대 기울기의 직선을 찾아야 합니다.
- 아래에서는 노란색 실선을 최대한 돌려 주황색 점선을 만드는 것이 상한일 것입니다.
- 결국 상한은 빨간색, 초록색 들의 점 중 하나씩을 접한다는 것을 알 수 있습니다.

![입력이 `0 1 0 0 1`인 경우](https://static.solved.ac/arena/editorial/3/gs2.png)

먼저 브루트 포스를 하게 되면 Monotone Chain의 최대 점의 개수는 〈[Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183)〉에 따라 $N^{2/3}$임을 알 수 있습니다. 즉, 각각의 점의 개수가 $N^{2/3}$을 넘지 않고, 가능한 모든 쌍을 조합해 검사하면 $\mathcal{O}\left({N^{4/3}}\right)$에 해결 가능합니다. 따라서 점을 $\mathcal{O}\left({N}\right)$에 찾고, $\mathcal{O}\left({N^{4/3}}\right)$에 문제를 풀 수 있습니다.

두 번째로 투 포인터 방법은, 위쪽 monotone chain의 가장 오른쪽 점 $A$와 아래쪽 monotone chain의 가장 왼쪽 점 $B$를 시작점으로 하여 선분을 그렸을 때, 위쪽 monotone chain과 만난다면 점 $A$를 위쪽 monotone chain 바로 직전의 점으로 업데이트하고, 반대로 아래쪽 monotone chain 바로 다음 점으로 점 $B$를 업데이트합니다. 이 과정을 계속 수행하다가 성공하는 시점을 출력하면 됩니다. 이 방법은 monotone chain을 $\mathcal{O}\left({N}\right)$에 찾고, $\mathcal{O}\left({N}\right)$에 해결 가능하므로 총 $\mathcal{O}\left({N}\right)$에 해결 가능합니다.
 
## 풀이 2

작성 예정

문제를 요약하면, 다항식을 다른 다항식으로 보내는 일종의 연산자 $S$를

$$
[S(q)](n):=\sum_{k=1}^nq(k)
$$

로 정의할 때, $[S^K(q)](n)$의 계수들을 $P$로 나눈 나머지를 구하는 문제가 됩니다.

## 풀이 1

다음의 식을 관찰합시다.

$$
\begin{aligned}
&\sum_{k=1}^nk\times(k-1)\times\cdots\times(k-s+1)\\
=\ &\frac{1}{s+1}\times(n+1)\times n\times(n-1)\times\cdots\times(n-s+1) \qquad (s \geq 1).
\end{aligned}
$$

이에 대한 증명은 우변에 $n$을 대입한 것에서 $(n-1)$을 대입한 것을 빼는 것으로 할 수 있습니다.

이를 활용하기 위하여, polynomial basis $\{1,\,n,\,n(n-1),\,\ldots,\,n(n-1)\cdots(n-d+1)\}$를 구성한 뒤 주어진 다항식을 이들의 선형결합으로 우선 분해합니다. 그러면

$$
q(n)=c_0+c_1n+c_2n(n-1)+\cdots+c_dn(n-1)\cdots(n-d+1)
$$

의 형태가 만들어집니다.

위의 공식을 활용하면, 상수항을 제외한 각 항에 대해 다음이 성립함을 확인할 수 있습니다:

$$
\begin{aligned}
[S^K(c_in(n-1)\cdots(n-i+1))](n) &= c_i\cdot i!{n+K\choose i+K} \\
&=c_i{i+K\choose i}^{-1}\times\left[\frac{(n+1)(n+2)\cdots(n+K)}{K!}\right]. \qquad (i\geq1) \\
\end{aligned}
$$
- 여기서 두 번째 변의 이항계수 ${n+K\choose i+K}$는 symbolic expression입니다.
- 참고: [Binomial coefficients as polynomials](https://en.wikipedia.org/wiki/Binomial_coefficient\#Binomial_coefficients_as_polynomials)

$\sum_{k=1}^n1$은 $(n+1)$이 아니라 $n$이 되기 때문에, 상수항에 대해서는 공식이 약간 바뀝니다. 위의 공식을 $i=0$에 대해서까지 적용하여 전부 더한 뒤, $c_0{n+K-1\choose K-1}$을 빼 주어야 정확한 답이 됩니다.
 
두 번째 변까지만을 활용하여

$$
[S^K(q)](n)=\left[\sum_{i=0}^dc_i\cdot i!{n+K\choose i+K}\right]-c_0{n+K-1\choose K-1}
$$

을 계산해도 되고(이때 각 $i$에 대하여 ${n+K\choose i+K}$를 순차적으로 구할 수 있습니다), 또는 세 번째 변까지 구하여 $c_i$들을 $c_i{i+K\choose i}^{-1}$로 대체한 다항식을 새로 구한 뒤, 거기에

$$
\frac{(n+1)(n+2)\cdots(n+K)}{K!}
$$

를 곱해 주어도 됩니다(여전히 상수항 처리는 필요합니다).

시간복잡도는 $c_i$들을 구하기 위해 $\mathcal{O}\left({d^2}\right)$, $K$차 다항식을 만들어내기 위해 $\mathcal{O}\left({K^2}\right)$, 다항식을 곱하기 위해 $\mathcal{O}\left({dK}\right)$가 각각 소요됩니다.
 
## 풀이 2

$\sum_{k=1}^nq(k)$를 풀어서 $q(1)+q(2)+\cdots+q(k)$로 쓰고, $\sum_{k=1}^n\sum_{j=1}^kq(j)$를 풀어서 $(q(1))+(q(1)+q(2))+\cdots+(q(1)+q(2)+\cdots+q(n))$으로 쓰는 식으로 다중 합의 모든 항을 열거했을 때, 각 $q(k),\,k=1,\,2,\,\ldots,\,n$이 몇 번씩 등장하는지를 셀 수 있습니다.

특히 $n$에서 시작하여 $k$로 끝나는 길이 $K$의 단조감소수열 하나마다 $q(k)$ 항 하나가 대응되는데, 이를테면 $K=3,\,n=3$일 때 수열 $(3,\,2,\,2)$에 대응하는 $q(2)$ 항은

$$
[\{q(1)\}]+[\{q(1)\}+\{q(1)+q(2)\}]+[\{q(1)\}+\{q(1)+\underline{q(2)}\}+\{q(1)+q(2)+q(3)\}],
$$

즉 $3$번째 대괄호 안의 $2$번째 중괄호 안의 $2$번째 항입니다. 따라서 $[S^K(q)](n)=\sum_{k=1}^nc_kq(k)$임을 얻습니다.
- $c_k$는 주어진 $(n-k+1)$개의 수로 이루어지는 길이 $K-1$의 단조감소수열의 개수입니다.
- $c_k$는 다시 중복조합 $ _{n-k+1}H_{K-1}={n+K-k+1 \choose K-1}$으로 얻어집니다.

결국 다음과 같은 풀이가 성립합니다.

- $q(n)$에 $1\sim(d+K)$를 대입하여 함숫값들을 얻습니다.
- 이 값들로부터 위 공식을 써서 $n=0,\,1,\,\ldots,\,(d+K)$에 대한 $[S^K(q)](n)$을 구할 수 있습니다.
  - 이항계수를 빠르게 구하기 위해 계승의 모듈러 값들을 전처리해 둡니다.
- 여기까지의 시간복잡도는 $\mathcal{O}\left({(d+K)^2}\right)$이고, 이제 이 $(d+K+1)$개의 함숫값으로부터 interpolation을 통해 다항식 $S^K(q)$를 복원하면 됩니다.
- 마지막의 interpolation은 , $x=0,\,1,\,\ldots,\,d+K$에 대한 함숫값들이므로, 구해 둔 함숫값들이 특수하기에 Newton's interpolation을 적용하기 좋고, $\mathcal{O}\left({(d+K)^2}\right)$에 완수할 수 있습니다.
  - 참고: [Newton Polynomial Application](https://en.wikipedia.org/wiki/Newton_polynomial\#Application)


우선 한 바구니에 $n$ 개의 빨래가 들어있는 경우, 걸리는 시간의 기댓값을 구해야 합니다.

한 바구니에서 임의의 두 개의 빨래를 동시에 빨래할 확률은 ${1\over 2}$입니다. 이는 귀납적으로 증명할 수 있습니다.
- 우선 $n$이 $2$인 경우 두 빨래를 같이 하는 경우 혹은 따로 하는 경우의 $2$가지 졍우가 있으므로, 확률은 ${1\over 2}$입니다.
- $n<m$인 $2$ 이상의 모든 자연수 $n$에 대해 성립한다고 가정합시다. 빨래의 개수가 $m$인 경우의 확률을 계산합니다.
  $$
  f(m)={1\over m}\sum_{i=1}^{m}\left({i(i-1)\over m(m-1)} + {(m-i)(m-i-1)\over m(m-1)}f(m-i)\right)
  $$
- 이때 $f(m-i)={1\over 2}$이기에 다음과 같이 정리할 수 있습니다.
  $$
  \begin{aligned}
  & {1\over m}\sum_{i=1}^{m}\left({i(i-1)\over m(m-1)} + {(m-i)(m-i-1)\over m(m-1)}f(m-i)\right) \\
  =\ &{1\over m}\sum_{i=1}^{m}\left({i(i-1)\over m(m-1)} + {(m-i)(m-i-1)\over 2m(m-1)}\right) \\
  =\ &{1\over m^2(m-1)}\sum_{i=1}^{m}\left(i(i-1) + {1\over 2}(m-i)(m-i-1)\right) \\
  =\ &{1\over m^2(m-1)}\left(\sum_{i=1}^{m}i(i-1) + {1\over 2}\sum_{i=0}^{m-1}i(i-1)\right) \\
  =\ &{1\over m^2(m-1)}\left({m(m+1)(m-1)\over 3} + {m(m-1)(m-2)\over 6}\right) = {1\over 2}
  \end{aligned}
  $$
- 즉, 귀납적으로 한 바구니내의 임의의 두 빨래를 같이 빨래할 확률은 $1\over 2$임을 증명할 수 있습니다.

$n$개의 빨래가 들어있는 바구니, 각 빨래의 무게를 $x_1$, $x_2$, $\cdots$, $x_n$이라고 합시다. 바구니의 빨래를 마치는 데 걸리는 시간의 기댓값은

$$
{\frac{1}{2}{\displaystyle\sum_{i=1}^{n}x_i^2 + \left[\sum_{i=1}^{n}x_i\right]^2}}
$$

입니다.

$\displaystyle\sum_{i=1}^{n} x_i^2$은 바구니에 빨래를 어떻게 나누든 고정되는 값입니다. 그러므로 빨래를 바구니에 담을 때 $\left(\sum x_i\right)^2+c$만을 생각하면 됩니다. 이는 convex hull trick을 활용하면 $\mathcal{O}\left({N \log N}\right)$의 시간복잡도로 구할 수 있다.


문제를 간략화합시다. 원래는 키를 반올림하여 측정해야 하지만, 정수 $m$에 대해 $m\times10^{-3}\mathrm{cm}$ 꼴로 표현되는 가장 가까운 키로 버림하여 측정하는 것으로 바꾸어도 정답은 변하지 않음이 설명됩니다.

## $\mathcal{O}\left({N^4}\right)$ 솔루션

성장률이 기약분수 $\frac{q}{p}(\times10^{-3}\mathrm{cm}/\text{일})$로 표현되는 상수 성장률 성장이 설명하는 전일 대비 성장 데이터는 주기 $p$를 가지게 됩니다.

성장률이 $\frac{q}{p}$로 일정하더라도 키의 초기값이 달라짐에 따라 데이터도 변화하는데, 성장률이 일정하다면 한 순환마디를 '돌려' 다른 순환마디를 만들 수 있음을 보일 수 있습니다.

다음 예를 관찰합시다.
- $y=0.4x + 0.1$과 $y = 0.4x + 0.8$의 $x = 0,\,1,\,2,\,3,\,4,\,5$에서의 함숫값을 정수로 버림하면 각각 $0,\,0,\,0,\,1,\,1,\,2$ 및 $0,\,1,\,1,\,2,\,2,\,2$입니다.
- 이 두 수열의 계차를 구하면 $\frac{q}{p} = \frac{2}{5}$에 대한 서로 다른 두 순환마디 $[0,\,0,\,1,\,0,\,1],\,[1,\,0,\,1,\,0,\,0]$을 얻습니다.
- 첫 순환마디를 왼쪽으로 두 칸 `돌리면' 두 번째 순환마디가 될 것입니다.

한편 어떤 길이 $N$의 데이터가 한 상수 성장률 성장으로 설명된다고 할 때, 이는 $\frac{q}{p}$ ($p\leq N$) 꼴 성장률의 상수 성장률 성장으로도 설명될 수 있습니다. 이를 아래와 같이 증명합시다.

![길이 6의 데이터 0, 1, 0, 1, 0, 0$을 설명하는 기울기 $\frac{4}{9}$의 상수 성장률 성장](https://static.solved.ac/arena/editorial/3/gs3-3.png)

위의 도식은 길이 $6$의 데이터 $0,\,1,\,0,\,1,\,0,\,0$을 설명하는 기울기 $\frac{4}{9}$의 상수 성장률 성장을 표현한 것입니다.

같은 데이터를 설명하는 다른 상수 성장률 성장을 찾기 위해, 기울기를 유지한 채 직선이 어느 구간의 아래끝 $A$에 닿을 때까지 평행하게 내립니다. 이 직선은 여전히 데이터를 설명합니다.
- 직선을 $A$를 중심으로 시계방향으로 회전시킵니다. $A$보다 $x$-좌표가 작은 어떤 구간의 위끝에 닿거나, $A$보다 $x$좌표가 큰 어떤 구간의 아래끝에 닿을 때까지 진행합니다.
- 만약 다른 구간의 아래끝에 닿았을 경우, 이 직선은 여전히 데이터를 설명하며, 또한 $x$-좌표가 최대 $N$만큼 차이나는 두 정수점을 지나고 있기에 $\frac{q}{p}(p\leq N)$꼴 기울기를 가집니다. 그렇지 않은 경우, 찾은 점을 $B$라고 합시다.
- 반시계방향으로 같은 작업을 반복합니다. 만일 $A$보다 $x$-좌표가 큰 어떤 구간의 위끝에 처음으로 닿았을 경우, 그 점을 $C$라고 합시다(한 아래끝과 다른 위끝에 동시에 닿은 경우에는 위끝을 생각합니다).
- 이제 $\overleftrightarrow{BC}$와 평행하고 $A$를 지나는 직선은 기울기가 $\overleftrightarrow{BA}$의 기울기 초과 $\overleftrightarrow{AC}$의 기울기 미만이 되므로, $B$와 $C$의 구성에 의해 이 직선은 데이터를 설명합니다.

이외에도 성장률이 정수 $n$과 $n+1$ 사이가 되는 상수 성장률 성장이 설명하는 데이터에는 오직 $n$과 $n+1$만이 등장할 수 있음을 관찰할 수 있습니다.

이제 문제는 다음과 같이 요약됩니다:
- $0$ 이상 $9$ 이하이며 기약분수로 표현했을 때 분모가 $N$ 이하인 모든 유리수 성장률에 대하여, 해당 성장률의 순환마디를 적당히 '돌리고' 무한 번 반복한 후 주어진 데이터와 비교하여 LCS를 구할 때, $N - \left(\text{LCS 길이}\right)$의 최솟값을 구하여 출력하고, 해당 최솟값의 $\argmin$이 되는 성장에 대해 데이터에서 LCS에 포함되지 않는 값들을 전부 출력합니다.

Naive하게 생각하면, 따져야 할 성장률은 $\mathcal{O}\left({N^2}\right)$개이며, 길이 $p$의 순환마디를 돌리는 방법이 $\mathcal{O}\left({p}\right)$가지, 다시 데이터와 LCS를 구하기 위해 각 경우마다 $\mathcal{O}\left({N}\right)$의 연산이 소요됩니다. 분모가 $N$ 이하인 기약분수 하나를 뽑을 때 그 분모의 기댓값이 $\frac{N}{2}$ 정도 또는 그 이상이라고 어림잡으면, 결국 이는 $\mathcal{O}\left({N^4}\right)$에 동작할 것이라고 볼 수 있습니다. 다만, $N\leq500$임을 감안하면 이는 비효율적입니다.

## $\mathcal{O}\left({N^3}\right)$ 솔루션

문제를 더 효율적으로 해결하기 위해서는 성장률의 순환마디가 갖는 규칙성을 부가적으로 파악해야 합니다. 이는 다음과 같이 표현됩니다.

![2와 3 사이의 유리수들을 포함하는 Stern-Brocot tree를 다른 형태로 그린 것](https://static.solved.ac/arena/editorial/3/gs3-4.png)

위 그림은 $2$와 $3$ 사이의 유리수들을 포함하는 Stern-Brocot tree를 다른 형태로 그린 것입니다(물론 일반적으로 정수 $n$과 $n+1$ 사이의 유리수들을 포함하도록 그릴 수 있습니다). 그래프의 간선마다 위쪽 끝점이 아래쪽 끝점의 부모 노드가 된다고 하면, 제일 위의 두 노드 $2/1$, $3/1$을 제외한 노드들은 각각 왼쪽 부모와 오른쪽 부모 노드를 갖습니다.
 
먼저 정수 $q$에 대해 성장률 $q / 1$에 대응하는 노드의 순환마디를 $[q]$로 저장해둘 수 있습니다. 한 노드 $q / p$의 왼쪽 부모 노드 $ql / pl$ 및 오른쪽 부모 노드 $qr / pr$에 대하여, $p = pl + pr$, $q = ql + qr$이 성립합니다. 이와 함께 두 부모 노드의 순환마디가 저장되어 있을 때, 다음이 성립합니다:

- **순환마디 규칙**: $ql / pl$의 저장된 순환마디를 왼쪽, $qr / pr$의 저장된 순환마디를 오른쪽에 두고 이어붙여 만든 길이 $pl + pr = p$의 열은 $q / p$의 순환마디가 된다.

이에 따르면, 깊이 우선 탐색과 유사한 과정을 통해 재귀적으로 모든 유리수 성장률에 대한 순환마디를 구할 수 있게 됩니다(모든 기약분수 성장률이 정확히 한 번씩 탐색되게 됩니다).

순환마디 규칙은 Farey sequence 내지는 Stern-Brocot tree의 특징적인 성질로부터 얻을 수 있습니다. 위의 그래프에 맞추어 이 성질을 서술하면 다음과 같습니다:
  - 한 노드 $q / p$와 그 부모 노드 $s / r$에 대하여, $|ps - qr| = 1$이 성립한다.

노드 $q / p$와 그 왼쪽, 오른쪽 부모 노드들 $ql / pl$, $qr / pr$이 주어진다고 가정합시다. 좌표평면 위에 세 점 $O(0,\,0)$, $A(pl,\,ql)$, $B(p,\,q)$를 그리고 세 점을 꼭짓점으로 하는 삼각형을 그려 봅시다. $\overleftrightarrow{OA}$의 기울기는 $ql / pl$이고, $\overleftrightarrow{AB}$의 기울기는 이보다 큰 $qr / pr$임에 유의합니다.

위 Stern-Brocot tree의 성질에 의하여 $\triangle OAB$의 넓이는 $\frac{1}{2}$입니다. 여기서 픽의 정리를 적용해 봅시다.
- $q / p,\,ql / pl,\,qr / pr$이 전부 기약분수이므로 삼각형의 변에 놓인 점 개수는 $3$개이고, 따라서 삼각형의 넓이는 $\left(\text{삼각형 내부의 점 개수}\right)+\frac{3}{2}-1$로도 표현됩니다.
- 이 둘을 동일시하면, $\triangle OAB$ 내부에는 격자점이 놓이지 않음을 보일 수 있습니다.

이제 두 곧은 경로 $O\rightarrow B$, $O\rightarrow A\rightarrow B$를 실제 성장을 나타내는 시간-키 함수의 그래프로 보고 이 두 성장이 설명하는 데이터를 추출하면, 두 경로 사이에 격자점이 놓이지 않는 상황에서 각 정수 $x$-좌표마다의 두 함숫값을 가까운 정수로 버림하고 있으므로 두 데이터는 온전히 일치합니다.

따라서 키의 초깃값이 정수이고 성장률이 $q / p$인 상수 성장률 성장이 설명하는 데이터의 앞 $p$개의 항은, 키의 초깃값이 정수이고 성장률이 각각 $ql / pl,\,qr / pr$인 상수 성장률 성장이 설명하는 데이터들의 앞 $pl,\,pr$개의 항들을 이어붙인 것과 일치합니다. 이를 다르게 표현하면 곧 순환마디 규칙이 됩니다.

하지만, 우리는 각 $q / p$의 순환마디를 알아내야 할 뿐만 아니라, 그 순환마디를 '돌린' 것의 무한반복과 입력받은 데이터 사이의 LCS 길이를 구하고, 그렇게 얻은 모든 $N - \left({\text{LCS 길이}}\right)$ 중 최소를 찾아야 합니다.

이는 DP를 활용하여 해결할 수 있습니다. 두 부모 노드들에 대해 일정한 정보들이 저장되어 있으면, 그 자식 노드에 대해 같은 정보를 $\mathcal{O}\left({N}\right)$에 저장할 수 있도록 할 것입니다. 그 정보로부터 원하는 값을 $\mathcal{O}\left({N}\right)$에 찾아낼 것입니다.
 
성장률 $q / p$에 대하여, 다음의 $2$가지 정보를 배열에 저장합니다.
- 첫 번째 정보는 크기 $p$의 정보입니다.
  - 각 $i=0,\,1,\,\ldots,\,p-1$에 대하여, 순환마디의 오른쪽 $i$개 항만 취하여 부분열을 만들고, 이 열을 데이터의 초항부터와 비교하여 LCS를 구해 나갑니다.
  - 만일 그러다가 데이터의 끝에 도달한다면, 그렇다는 사실과 함께(`true`) 해당 부분열의 몇 개의 원소까지 데이터 안에 '집어넣을' 수 있는지가(`int`) 저장될 것입니다.
  - 만일 해당 열 전부를 데이터 안에 '집어넣었지만' 데이터의 오른쪽 끝에 도달하지 못했다면, 그러지 못했다는 사실과 함께(`false`) 부분열을 모두 '집어넣고' 나서 데이터의 몇 번째 항에 도달했는지가(`int`) 저장될 것입니다.
- 두 번째 정보는 크기 $n$의 정보입니다.
  - 각 $i=0,\,1,\,\ldots,\,n-1$에 대하여, 이번엔 순환마디 전체를 데이터의 $i$번째 항부터와 비교하여 LCS를 구해 나갑니다. 저장되는 정보는 $1$번째 정보와 동일합니다(`bool`, `int` 하나씩).

부모 $ql / pl$, $qr / pr$의 정보들로부터 $q / p$에 대한 $1$번째 정보를 다음과 같이 $\mathcal{O}\left({N}\right)$에 저장할 수 있습니다. 두 번째 정보를 저장하는 방식은 유사하므로 생략합니다.
 
- $q / p$의 순환마디는 길이가 $pl$인 $ql / pl$의 순환마디와 길이가 $pr$인 $qr / pr$의 순환마디를 이어붙인 것과 같습니다.
  - 따라서 $0\leq i<pr$에 대하여, $q / p$의 순환마디의 오른쪽 $i$개 항을 취하면 그것은 $qr / pr$의 순환마디의 오른쪽 $i$개 항과 같습니다. 즉, $qr / pr$의 $1$번째 정보의 $i$번째 값을 그대로 가져와 저장하면 됩니다.
- $i\geq pr$이라면, $q / p$의 순환마디의 오른쪽 $i$개 항은 $ql / pl$의 순환마디의 오른쪽 $(i-pr)$개 항과 $qr / pr$의 순환마디를 이어붙인 것과 같습니다.
  - $ql / pl$의 $1$번째 정보의 $(i-pr)$번째 값을 가져옵니다. 그 값이 `false`라면, 연관 있는 `int` 값은 데이터 상의 항 번호가 될 것입니다.
  - $qr / pr$의 $2$번째 정보의 해당 `항 번호'번째 값을 다시 가져옵니다. 그 값이 `false`라면, 연관 있는 `int` 값을 저장하면 됩니다.
- $i$를 $pr$부터 하나씩 늘리다 보면 두 번째로 찾은 값이 `true`가 될 수 있습니다. 그렇다면 그때부터는 데이터에 '집어넣은' 부분열의 원소 개수를 $(i-pr)$과 두 번째 `int` 값의 합으로 구할 수 있습니다.
- $i$를 더 늘리다 보면 첫 번째로 찾은 값조차 `true`가 될 수 있습니다. 그렇다면 그때부터는 데이터에 '집어넣은' 부분열의 원소 개수는 첫 번째 `int` 값으로서 구할 수 있습니다.
  
이제 이렇게 저장되어 있는 $q / p$의 정보로부터, $q / p$ 성장률의 순환마디를 '돌리고' 무한 번 반복한 후 주어진 데이터와 비교한 LCS 길이를 순환마디를 몇 번 '돌렸는지'에 따라 전부 구해낼 것입니다.
- 각 $i = n-1,\,\ldots,\,0$에 대하여, '돌리지' 않은 성장률의 순환마디를 무한 번 반복한 후 주어진 데이터의 $i$번째 항부터와 비교한 LCS 길이를 순차적으로 구할 것입니다.
- 이를 위하여, 주어진 $i$에 대해 $2$번째 정보의 $i$번째 값을 가져옵니다.
  - 만약 그 값이 `true`라면, 그 `int` 값을 사용하면 됩니다.
  - 만약 `false`라면, 순환마디를 데이터에 '집어넣은' 후의 데이터 상에서의 위치 $j$가 있으니, 그 $j$에 대해 구해 놓은 값에 순환마디 하나의 길이 $p$를 더한 값을 사용하면 됩니다.
- 이 값들을 모두 구했다면, 이로부터 유사한 방식으로 각 $i = 0,\,1,\,\ldots,\,p-1$에 대하여, 순환마디를 $i$회 왼쪽으로 '돌리고' 무한 번 반복한 후 주어진 데이터의 초항부터와 비교한 LCS 길이를 얻을 수 있습니다($1$번째 정보를 적절히 활용합니다).
- 각 $q / p$에 대하여 위의 정보 저장, LCS 길이 도출 과정 전부가 $\mathcal{O}\left({N}\right)$에 동작합니다.
 
초기에 데이터를 입력받으면, 각 $n=0,\,1,\,\ldots,\,8$에 대하여 $n$과 $n+1$만 남긴 sub-data를 형성한 뒤, $n$과 $n+1$ 사이의 분모가 길이(sub-data) 이하인 성장률들에 대해 위의 DP 과정을 거칩니다.

이로부터 고려해야 할 모든 성장에 대한 $N - \left(\text{LCS 길이}\right)$의 최솟값을 찾고, 그 $\argmin$이 되는 성장을 같이 찾습니다. 이 과정은 결국 $\mathcal{O}\left({N^2}\right)$개의 성장률마다 $\mathcal{O}\left({N}\right)$회, 총 $\mathcal{O}\left({N^3}\right)$회의 연산 내에 완수됩니다($0,\,1,\,\ldots,\,9$의 정수 성장률들도 처리해야 함에 유의합니다).

최솟값을 출력하고, 해당 성장으로부터 데이터를 복원하여 주어진 데이터와 비교한 LCS를 구합니다. 주어진 데이터에서 LCS에 포함되지 않은 항들을 제거(즉, 출력)하고 나면, 데이터의 남은 부분은 상수 성장률 성장으로 설명될 것입니다.
 