Interference Output Only Compilation commands

Wikipedia에 따르면, '자기상관'이란 신호의 교차상관관계를 말한다. 높은 자기상관값을 가지는 것은 혼선을 증가시키므로 무선 신호에 좋지 않다. 만약 당신이 미래에 신호를 다루는 무선 통신 연구원이 되기로 결정한다면, 당신은 아마도 다음 문제에 직면하게 될 것이다.

모든 원소가 -1 또는 1인 이진 수열 $S = (s_{1}, s_{2}, ..., s_{N})$를 고려해 보자. $S$의 자기상관함수 $C_{k}(S)$는 다음과 같이 정의된다.

$C_{k}(S) = \sum_{i=1}^{N-k} s_{i} s_{i+k}$ ( $k = 1 ... N-1$ )

$S$의 에너지는 다음과 같이 정의된다.

$E(S) = \sum_{k=1}^{N-1} C_{k}^{2}(S)$

문제는 $E(S)$가 최소화되도록 $s_i$들의 값을 결정하는 것이다.

길이가 $N = 11$인 이진 수열 $S = (1, 1, 1, -1, -1, -1, 1, -1, -1, 1, -1)$을 생각해 보자. 이 수열은 최소의 자기상관값들 $C_{k}(S) ( k = 1 ... N-1 ) $를 가져 $E(S)=5$가 된다. 이것이 길이가 $N = 11$인 모든 가능한 이진 수열들 중 최소의 $E(S)$이다. 이것은 더욱 균일한 스펙트럼을 만들고, 사람들에게 더 나은 성능을 제공한다.

당신이 이 문제를 빠르게 이해할 수 있도록 하기 위해서, 여기에 중간 계산 과정이 있다.

S = (1, 1, 1, -1, -1, -1, 1, -1, -1, 1, -1)
N = 11
C1 (S) =  0 ==> 제곱 ==> 0
C2 (S) = -1              1
C3 (S) =  0              0
C4 (S) = -1              1
C5 (S) =  0              0
C6 (S) = -1              1
C7 (S) =  0              0
C8 (S) = -1              1
C9 (S) =  0              0
C10(S) = -1              1
                        --- +
                  E(S) = 5

이 수열 $S$는 Run Length Notation (RLN)으로 쓸 수 있다. RLN에서의 각 숫자는 같은 부호를 가지는 연속한 원소들의 개수를 나타낸다. $S$에는 3개의 +1, 3개의 -1, 1개의 +1, 2개의 -1, 1개의 +1, 그리고 1개의 -1이 있으므로, RLN으로는 "331211"로 쓸 수 있다.

만약 10 이상의 수를 쓸 필요가 있다면, 이는 A, B, C, ... 등으로 나타내어라. 36 이상의 수를 쓸 필요는 없다는 것을 보장한다.

서브태스크

아래 표에서 각 행은 서브태스크 하나를 나타낸다. 각 서브태스크마다 배점은 10점으로 동일하다.

서브태스크	$N$	$T$
1	20	26
2	21	26
3	27	37
4	28	50
5	40	108
6	50	153
7	55	171
8	77	366
9	80	400
10	100	722

제출할 때의 파일명은 interference.outX.1의 형식이어야 한다. (단, X는 서브태스크의 번호다.) 채점 전, 당신은 모든 파일들을 압축하여 zip 파일 형식으로 제출해야 한다.

채점 서버는 파일의 압축을 해제하여, 각 서브태스크마다 다음과 같은 과정을 거쳐 점수를 매긴다.

1. RLN을 이진 수열로 바꾼다.
2. RLN이 유효하지 않다면, 즉 각 숫자의 합이 $N$과 다른 경우라면, 해당 서브태스크의 점수는 자동적으로 0이 된다는 점을 명심하라.
3. $E(S)$의 공식에 따라 계산한다.
4. 해당 서브태스크의 점수는 $10^{T/E(S)}$점을 소숫점 셋째 자리에서 반올림한 값이 된다.