휴대전화 문자 입력 최적화
시간 제한1초메모리 제한128 MB
26개의 알파벳을 순서를 유지한 채 K개의 연속 블록(블록당 최대 8개)으로 나누어 빈도 가중 키 입력 횟수의 평균을 최소화하고, 동률이면 사전순으로 가장 작은 배열을 출력하는 문제입니다.
문제
표준 휴대전화 키패드는 여러 알파벳을 하나의 숫자 키에 차례대로 배정한다. 한 키에 배정된 글자들 중 앞에서 j번째 글자를 입력하려면 그 키를 j번 눌러야 한다. 예를 들어 한 키에 A, B, C가 순서대로 배정되어 있으면 C를 입력하려면 그 키를 세 번 누른다.
A부터 Z까지 각 알파벳의 사용 빈도와 사용할 숫자 키의 개수 K가 주어진다. 알파벳의 순서는 반드시 유지해야 하므로, 각 키에는 연속한 알파벳 구간만 배정할 수 있다. 각 키에는 적어도 한 글자, 많아야 여덟 글자를 배정해야 한다.
입력해야 하는 평균 키 입력 횟수가 최소가 되도록 알파벳을 K개의 키에 배정하라. 평균은 각 알파벳의 입력 횟수에 그 알파벳의 사용 빈도를 곱한 값의 합을 전체 빈도 합으로 나눈 값이다.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 키의 개수 K가 주어진다. (4 <= K <= 26) 둘째 줄에는 A부터 M까지 13개 알파벳의 사용 빈도가 주어진다. 셋째 줄에는 N부터 Z까지 13개 알파벳의 사용 빈도가 주어진다.
출력
각 테스트 케이스마다 한 줄을 출력한다. 먼저 최적 배정에서의 평균 키 입력 횟수를 소수점 아래 셋째 자리까지 출력하고, 이어서 A부터 Z까지의 배정을 나타내는 K개의 문자열을 공백으로 구분해 출력한다. 각 문자열은 하나의 키에 배정된 연속한 알파벳들을 의미한다.
최소 평균이 같은 배정이 여러 개라면, K개의 문자열을 공백 하나로 이어 붙인 문자열이 사전순으로 가장 작은 배정을 출력한다.