바코드

Code-11은 주로 통신 장비에 붙이는 라벨에 쓰이는 문자 인코딩 바코드 방식이다. 인코딩할 수 있는 문자는 숫자 0부터 9까지, 대시(-), 그리고 모든 Code-11 바코드의 앞뒤에 붙는 특수한 시작/종료 문자이다.

Code-11은 이산 방식이며 각 문자는 독립적으로 인코딩된다. 한 문자는 어두운 막대로 시작하여 밝은 막대와 어두운 막대가 번갈아 나오는 인접한 5개의 영역(막대)으로 표현된다. 각 막대는 아래 표에 따라 좁거나 넓으며, 0은 좁은 막대, 1은 넓은 막대를 뜻한다.

문자 1은 넓은 어두운 막대, 좁은 밝은 막대, 좁은 어두운 막대, 좁은 밝은 막대, 넓은 어두운 막대 순으로 인코딩된다. 각 문자의 바코드 뒤에는 문자를 구분하기 위한 좁은 밝은 막대가 온다.

두 가지 너비만 쓰는 인코딩은 단순하다. 판독기는 좁은 막대와 넓은 막대만 구별하면 되므로, 인쇄 품질이 낮아도 인쇄 편차를 많이 허용한다.

오류를 검출하려고 이 Code-11 바코드에는 메시지 끝(시작/종료 문자 직전)에 검사 문자 C와 K를 두 개 추가한다. 왼쪽부터 인코딩할 n개의 문자를 c_1부터 c_n이라 하면, C 검사 문자의 값은 다음과 같다.

$\left(\sum_{i=1}^{n}\left((n - i) \bmod 10 + 1\right) \times w(c_i)\right) \bmod 11$

여기서 w(c_i)는 문자 c_i의 가중치다. 숫자 0부터 9의 가중치는 0부터 9이고, 하이픈의 가중치는 10이다. (mod는 +보다 우선한다.)

K 검사 문자의 값은 다음과 같다.

$\left(\sum_{i=1}^{n+1}\left((n - i + 1) \bmod 9 + 1\right) \times w(c_i)\right) \bmod 11$

여기서 c_{n+1}은 C 검사 문자다. 예를 들어 메시지가 123-45이면 C는 5이고 K는 2이다. 123-4552 여덟 문자의 바코드 앞뒤에 시작/종료 문자 바코드를 붙이면 완전한 Code-11 바코드가 된다.

간단한 바코드 리더는 수백 개의 작은 CCD 센서로 이루어진 선형 배열로 바코드에서 반사된 빛을 측정한다. 각 센서는 밝음 또는 어두움만 보고한다. 소프트웨어는 밝은 영역과 어두운 영역을 구분하고, 그 너비로 바코드를 검증하여 인코딩된 정보를 얻는다. 바코드의 방향은 고정되어 있지 않으므로, 소프트웨어는 왼쪽에서 오른쪽으로 스캔된 바코드든 오른쪽에서 왼쪽으로 스캔된 바코드든 해독할 수 있어야 한다.

이 문제는 판독기가 감지한 밝은 영역과 어두운 영역의 너비로부터 바코드를 해독하는 것이다. 넓은 막대는 좁은 막대의 두 배 너비가 되도록 의도된 것이다. 프린터마다 차이가 있어서 막대의 너비는 의도한 값보다 최대 5퍼센트 넓거나 좁을 수 있다. 길이가 0인 메시지는 없다.

입력에는 여러 개의 테스트 케이스가 들어 있으며, 각 케이스는 바코드 리더가 한 번 스캔한 결과에 해당한다. 각 케이스는 감지된 영역의 수 $m \le 150$으로 시작한다. 이어서 각 영역의 센서 수 $d_1 \ldots d_m$이 주어지며, $1 \le d_i \le 200$이다. 한 영역의 센서들은 모두 같은 빛의 세기를 보고한다. 각 케이스의 데이터는 어두운 막대로 시작해서 어두운 막대로 끝나며, 앞뒤에 여백은 없다.

마지막 테스트 케이스 뒤에는 정수 0이 하나 주어진다.

각 입력 케이스마다 케이스 번호와 해독 결과를 한 줄에 출력한다. 바코드를 성공적으로 해독하면 검사 문자를 뺀 메시지 문자를 출력한다. 해독은 성공했지만 C 검사 문자가 틀렸다면 bad C를 출력한다. 해독에 성공하고 C 검사 문자는 맞았지만 K 검사 문자가 틀렸다면 bad K를 출력한다. 막대 너비가 허용 범위를 벗어나거나, 시작/종료 코드가 없거나 잘못되었거나, 그 밖의 잘못된 조건으로 해독할 수 없다면 bad code를 출력한다. 출력 형식은 주어진 출력 예시를 따른다.