시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 17 5 5 29.412%

문제

상근이는 팩스 이미지를 압축하는 계획을 만드려고 한다. 스캐너를 통해서 이미지를 입력받으면, 1과 256사이의 숫자로 이루어진 수열로 변환된다. 예를 들어, 아래와 같은 수열로 이미지를 변환할 수 있다.

1, 1, 1, 1, 1, 46, 1, 1, 1,1, 1, 1, 2, 1, 2, 1, 1, 25, 26, 25, 25, 255, 256, 256, 256, 255,...

이미지를 반드시 정확하게 변환할 필요는 없다. 따라서, 상근이는 수열의 각 숫자를 레벨 4개(1, 86, 172, 256)으로 나타내려고 한다. 그리고, 이 레벨은 다음과 같이 2-bit 코드로 나타낼 수 있다.

Level 1 86 172 256
Code 00 01 10 11

그림 안에는 같은 색으로 이루어진 영역(예를 들면 공백)이 있다. 이 영역을 변환하면 유사한 숫자들이 연속해서 나타난다. 이를 처리하기 위해서 다음과 같은 압축 방법을 사용하려고 한다.

  1. 수열의 첫 번째 숫자는 위의 표에 나온 2bit 코드로 변환한다.
  2. 그 다음에 나오는 다른 모든 숫자에 대해서는
    • 만약 수열의 바로 앞에 있는 숫자가 같은 숫자라면 0으로 변환한다.
    • 앞에 있는 숫자와 다른 숫자라면 1을 앞에 붙인 뒤 위 표의 2bit 코드로 변환한다.

상근이는 작은 양의 에러를 크게 신경쓰지 않기 때문에, 작은 양의 에러는 무시한다. 예를 들어, 입력된 수열이 2, 2, 2, 2, 2, 46, 2, 2 라고 했을 때, 이를 1, 1, 1, 1, 1, 86, 1, 1로 나타낸 다음 변환하면 0000001011000가 되고 전체 에러는 1+1+1+1+1+40+1+1=47 이 된다. 하지만 1, 1, 1, 1, 1, 1, 1, 1 로 나타낸 후 변환하면 전체 에러는 1+1+1+1+1+45+1+1=52가 되어 커지지만 코드가 000000000가 되어 더 짧아진다.

상근이는 변환 비용을 최소로 하는 방법을 찾으려고 한다. 변환 비용은 전체 에러 + W*(변환 코드의 길이)로 계산할 수 있다.

  1. W는 에러와 코드의 길이 중 어느 것을 중요시 하느냐에 따라 입력으로 주어진다.
  2. 이 때 전체 에러는 입력 수열 x1, x2, , xN , 변환 수열 y1, y2, , yN에 대해서 다음과 같다. Σ|xi-yi|

수열이 2, 2, 2, 2, 2, 46, 2, 2 이고, W가 100인 경우에 y1,..., y8 = 1, 1, 1, 1, 1, 86, 1, 1 로 변환하면 코드는 0000001011000이 되고, 변환 비용은 47 + 100 * 13 = 1347이다. 하지만 y1,..., y8 = 1, 1, 1, 1, 1, 1, 1, 1로 변환하면 코드는 000000000이고 변환 비용은 52 + 100 * 9 = 952이다.

입력

첫째 줄에 수열의 길이 N(1 ≤ N ≤ 50), 가중치 W(1 ≤ W ≤ 100)가 주어진다. 다음 N개의 줄에는 수열을 이루는 숫자(≤256)들이 차례로 주어진다.

출력

첫줄에는 최소 변환 비용을 출력한다. 그리고 두 번째 줄에는 변환코드를 출력한다.

예제 입력

8 100
2
2
2
2
2
46
2
2

예제 출력

952
000000000

힌트