XCorr

길이가 동일한 수열 \(X=(x_0, x_1, \cdots, x_{n-1})\)와 \(Y=(y_0, y_1, \cdots, y_{n-1})\)가 있다.

이 두 수열의 각 원소는 음이 아닌 정수이다. 다음은 \(n=5\)인 경우의 한 예이다.

[\(X=(1{,}0{,}0{,}0{,}1)\)]

[\(Y=(0{,}5{,}2{,}0{,}1)\)]

임의의 정수 \(t\)가 주어졌을 때 \(XCorr(t)\)는 다음과 같이 정의된다.

[XCorr(t)=\displaystyle\$sum_{i=0}^{n-1}{x_iy_{i$+t}}]

(\(i<0\)이거나 \(i\geq n\)이면 \(x_\)i=y_i=0으로 간주한다.)

예를 들어 \(t\)가 \(0, 1, -1\)일 때, \(XCorr(t)\)값은 다음과 같이 계산된다.

[\(XCorr(0) = x_0y_0\) + x_1y_1 + \dots + \(x_{n-1}y_{n-1}\)]

[\(XCorr(1) = x_0y_1\) + x_1y_2 + \dots + \(x_{n-1}\)y_n]

회색 칸에 들어있는 부분은 계산결과에 영향을 주지 않음에 주의하라. \(y_0\)는 계산식에 포함되지 않고, \(x_{n-1}\)은 곱해지는 \(y_\)n=0 이므로 계산 결과에 영향을 주지 않는다. 따라서 예시 수열 \(X\)와 \(Y\)에서 \(XCorr(1)\)은 다음과 같이 계산할 수 있다.

[1\times5+0\times2+0\times0+0\$times1=5$]

[\(XCorr(-1) = x_0y_{-1}\) + x_1y_0 + \dots + \(x_{n-1}y_{n-2}\)]

임의의 \(t\)값의 범위 \((a \le t \le b)\)에 대해 \(XCorr(t)\)를 모두 구해서 더한 값 \(S(a,b)\)는 다음과 같이 정의된다.

[S(a,b)=\displaystyle\sum_{a \le t \le b}{XCorr(t)}]

수열 \(X\),\(Y\)와 \(t\)의 범위 \(a\), \(b\)가 주어졌을 때 \(S(a,b)\)를 구하는 프로그램을 작성하시오.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수열 \(X\)에서 0이 아닌 정수의 개수 \(N\)이 주어진다.(수열의 길이 \(n\)이 아님). 다음 \(N\)개의 줄에는 수열 \(X\)의 각 양의 정수 \(x_i\)에 대해 인덱스 \(i\) 와 \(x_i\) 값이 인덱스의 오름차순으로 주어진다. 다음 줄부터는 수열 \(Y\)가 \(X\)와 동일한 방식으로 주어진다. (\(Y\)에서 0이 아닌 정수의 개수 \(M\)이 주어지고 다음 \(M\)개의 줄에는 수열 \(Y\)의 각 양의 정수 \(y_i\)에 대해 인덱스 \(i\)와 \(y_i\) 값이 인덱스의 오름차순으로 주어진다.) 다음 줄에는 \(t\)의 범위의 최솟값인 정수 \(a\)가 주어지고, 그 다음 줄에는 \(t\)의 범위의 최댓값인 정수 \(b\) (\(a \le b\))가 주어진다.

표준 출력으로 \(S(a,b)=\displaystyle\sum_{a \leq t \leq b}{XCorr(t)}\) 값을 정수로 출력하라.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2018 > 2차 대회 > 고등부 1번