35264번 - Sonic Wave 스페셜 저지

아래는 Call for Tasks 당시 작성한 지문이다. 믿거나 말거나. 이 문제를 이해하고 선정한 파딱에게 박수를 보내주자. 쉬운 설명의 지문은 아래에 적어놓았다.

길이 $N$의 $1$차원 음향 복도를 정수 격자 $\Omega=\{1,2,\dots,N\}$ 로 모델링한다. 기록 시각 $T$에서 각 위치 $i\in\Omega$에서 관측된 음향 변위는 $y_i\in\mathbb Z$로 주어진다.

각 격자점에는 유한 개의 스피커를 설치할 수 있으며, 스피커 $j$는 위치 $x_j\in\Omega$, 방사 진폭 $v_j\in\mathbb Z\cap[1,2\times10^9]$, 그리고 이산 위상 $\phi_j\in \{0,1,2,3\}$를 갖는다.

스피커 $j$가 복도 위치 $i$에서 유도하는 음향 변위 $\Delta y_i^{(j)}$는 다음과 같이 정의된다. 헤비사이드 계단함수 $H:\mathbb R\to\{0,1\}$를 $H(t)= \begin{cases} 0 & t<0 \\ 1 & t\ge 0\end{cases}$ 로 정의한다.

$$\Delta y_i^{(j)} = \Biggl( \lim_{z \to 0^+} \frac{(1+z)^{v_j}-1}{z} \Biggr) \cdot \Biggl( \int_{0}^{1} H\bigl(i-x_j+1-s\bigr) ds \Biggr) \cdot \Biggl( \sum_{n=0}^{\infty} \frac{(-1)^n}{(2n+1)!} \left(\frac{\pi}{2}\right)^{2n+1} (i-x_j-\phi_j)^{2n+1} \Biggr)$$

기록 시각 $T$에서 관측된 음향 변위는 모든 스피커의 방사 효과가 선형적으로 중첩된 결과로, $ y_i=\sum_{j=1}^{M}\Delta y_i^{(j)}, \forall i\in\Omega $를 만족한다.

주어진 관측값 $y_1,y_2,\cdots,y_N$에 대해 위의 음향 변위 공식을 만족시키는 스피커 파라미터 집합을 구성하라. 단, 설치된 스피커의 총 개수 $M$이 최소가 되어야 한다.

아니 왜.

$1$차원 모양의 복도에는 $1$번부터 $N$번까지 칸이 있고, 어떤 순간에 각 칸의 수 $y_1, y_2, \cdots, y_N$를 기록했다. 이 수는 여러 개의 스피커 소리를 모두 합친 결과이다.

스피커 $1$개는 다음 규칙을 가진다.

• 스피커는 위치 $x$, 소리 세기 $v$, 소리 밀림 $\phi$를 가진다.
• 스피커는 현재 위치 $x$부터 오른쪽으로 한 칸씩 $[0, +v, 0, -v]$ 모양의 소리 패턴을 반복해서 각 칸에 소리의 영향을 준다.
  • $\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \text{위치} & \hline x + 0& x + 1& x + 2& x + 3& x + 4& x + 5& x + 6& x + 7& x + 8& x+9&\cdots\\\hline \text{영향} & 0 & +v & 0 & -v & 0 & +v & 0 & -v & 0 & +v & \cdots \\\hline \end{array}$
• $\phi$는 소리 패턴이 몇 칸 밀려서 시작하는지를 뜻한다.
  • $\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \text{위치} & \hline x + 0& x + 1& x + 2& x + 3& x + 4& x + 5& x + 6& x + 7& x + 8& x+9&\cdots\\\hline \phi=0 & 0 & +v & 0 & -v & 0 & +v & 0 & -v & 0 & +v & \cdots \\\hline \phi=1 & -v & 0 & +v & 0 & -v & 0 & +v & 0 & -v & 0 & \cdots \\\hline\phi=2 & 0 & -v & 0 & +v & 0 & -v & 0 & +v & 0 & -v & \cdots \\\hline\phi=3 & +v & 0 & -v & 0 & +v & 0 & -v & 0 & +v & 0 & \cdots \\\hline \end{array}$

기록값 $y_i$는 설치된 모든 스피커가 $i$번째 칸에 준 영향을 전부 합친 값이다. 주어진 $y_1, y_2, \cdots, y_N$을 만들 수 있는 스피커 배치가 궁금하다. 그중에서 설치한 스피커 수가 최소가 되는 스피커 배치를 찾아보자.

아래 [지문 보기] 텍스트를 클릭하면 엄격하게 정의를 설명한 지문을 볼 수 있다. 입력, 출력, 예제 설명은 엄격하게 정의를 설명한 지문을 기준으로 작성했음을 유의하라.

• 주요 차이점
  • 소리 세기 → 볼륨
  • 소리 밀림 → 위상
  • 스피커 $1$개의 $x$, $v$, $\phi$ → $j$번째 스피커의 $x_j$, $v_j$, $\phi_j$

첫째 줄에 $N$이 주어진다. $(1 \le N \le 1\,000\,000)$

둘째 줄에 $y_1$, $y_2$, $\cdots$, $y_N$이 공백으로 구분되어 주어진다. $(-10^9 \le y_i \le 10^9)$

주어진 입력에 대해 조건을 만족하는 스피커 배치가 항상 존재함이 보장된다.

첫째 줄에 설치한 스피커 최소 개수 $M$을 출력한다.

다음 $M$개 줄에 걸쳐 설치한 스피커 정보를 출력한다. 그중 $j$번째 줄에는 정수 $x_j$, $v_j$, $\phi_j$를 공백으로 구분하여 출력한다. $(1 \le x_j \le N$; $1 \le v_j \le 2 \times 10^9$; $0 \le \phi_j \le 3)$

만족하는 스피커 배치가 여러 개라면 그중 아무것이나 출력한다.