워드 클라우드

워드 클라우드는 글 데이터를 가중치에 따라 그림으로 보여 준다. 여기서 각 단어의 글꼴 크기는 그 단어가 자료에 몇 번 나왔는지로 정한다. 태그 존슨은 온라인 문서에 나오는 단어를 세는 사람이다. 그는 방문한 사이트마다 그 사이트에 나온 단어와 각 단어의 등장 횟수를 표로 정리해 두었고, 이 자료로 워드 클라우드를 만들려고 한다.

알고리즘을 설명하기 전에 조판 용어를 짚는다. 길이의 기본 단위는 포인트(pt)다. 글꼴 크기는 한 줄에서 다음 줄까지의 세로 길이를 포인트로 잰 값이고, 줄 사이 여백도 여기에 들어간다. 12pt 글꼴에서는 어떤 글자의 위쪽 끝에서 한 줄 아래 글자의 위쪽 끝까지가 12포인트다. 글자의 높이는 대문자든 소문자든 글꼴의 포인트 크기와 정확히 같다고 하자.

이 문제는 Courier처럼 모든 글자의 폭이 같은 고정폭 글꼴만 다룬다. 글자 하나의 폭은 글꼴 크기와 가로세로 비율로 정해진다. Courier에서 글자 $t$개로 이루어진 단어를 크기 $P$인 글꼴로 그리면 전체 폭은 $\left\lceil \frac{9}{16} \cdot t \cdot P \right\rceil$ 포인트다. 올림 기호에 주의한다. 다섯 글자 단어를 20pt 글꼴로 그리면 높이는 20포인트, 폭은 $\left\lceil \frac{900}{16} \right\rceil = \lceil 56.25 \rceil = 57$ 포인트다.

태그는 다음 방법으로 클라우드를 만든다. 단어 목록을 미리 정렬하고, 다섯 번보다 적게 나온 단어는 버린다. 남은 단어 $w$의 글꼴 크기는

$P = 8 + \left\lceil \frac{40(c_w - 4)}{c_{max} - 4} \right\rceil$

로 정한다. $c_w$는 그 단어의 등장 횟수, $c_{max}$는 자료에서 가장 많이 나온 단어의 등장 횟수다. 이 식에 따라 모든 단어는 9pt부터 48pt 사이의 글꼴로 그려진다. 그다음 주어진 순서대로 단어를 한 줄씩 위에서부터 채운다. 이웃한 두 단어 사이에는 가로 여백 10포인트를 둔다. 한 줄의 가로 길이 합은 클라우드의 폭 $W$를 넘을 수 없고, 그 한도 안에서 들어가는 만큼 한 줄에 단어를 채운다. 한 줄의 높이는 그 줄에 놓인 단어의 글꼴 크기 중 가장 큰 값이고, 클라우드의 높이는 각 줄 높이의 합이다.

입력은 자료 묶음 하나 이상으로 이루어진다. 각 묶음의 첫 줄에 정수 $W$와 $N$이 주어진다. $W$는 클라우드의 최대 가로 폭이고 $1 \le W \le 5000$이며, 어떤 단어를 그 단어의 글꼴 크기로 그려도 그 폭보다 좁지 않다. $N$은 클라우드에 들어가는 단어의 개수이고 $1 \le N \le 100$이다. 이어지는 $N$개의 줄에는 공백이 없는 문자열 $S$와 정수 $C$가 주어진다. $S$는 단어, $C$는 원래 자료에서 그 단어가 나온 횟수이며 $5 \le C \le 1000$이다. 단어는 클라우드에 놓이는 순서대로 주어진다. 입력의 마지막 줄에는 0이 두 개 주어지며, 이 줄은 자료 묶음이 아니다.

각 자료 묶음마다 한 줄에 CLOUD, 공백 하나, 묶음의 순번, 콜론, 공백 하나, 그리고 클라우드의 높이를 포인트 단위 정수로 출력한다. 순번은 1부터 시작해 입력에 나온 순서대로 1씩 커진다.