완전 해시

Perfect Software, Inc.는 고속 네트워크를 흐르는 텍스트에서 특정 단어가 나타나는지 검사하는 정부 계약을 맡았습니다. 이 시스템은 각 단어를 여러 개의 작은 완전 해시 테이블(perfect hash table) 과 대조하며, 여러분이 할 일은 각 테이블에 대한 완전 해시 함수를 만드는 것입니다.

완전 해시 함수는 모든 입력을 빈틈없이 꽉 찬 테이블로 곧바로 대응시킵니다(충돌도 없고 빈 칸도 없습니다). 해시 함수의 형태는 $\lfloor C / w \rfloor \bmod n$ 이며, 여기서:

• $C$ 는 여러분이 찾아야 하는 양의 정수이고,
• $w$ 는 입력 단어의 정수 표현이며,
• $n$ 은 테이블의 길이(목록에 있는 단어의 개수)입니다.

$C$ 는 가능한 한 작아야 합니다. 여기서 $\lfloor R \rfloor$ 는 $R$ 의 바닥 함수로, $R$ 이하인 가장 큰 정수를 뜻합니다.

$C$ 찾기. 단어 값들을 $W = \lbrace w_1, w_2, \ldots, w_n \rbrace$ 라 하고 $w_1 < w_2 < \cdots < w_n$ 이 되도록 정렬했다고 합시다. 다음을 만족하는 가장 작은 양의 정수 $C$ 를 찾으세요.

$$\left\lfloor \frac{C}{w_i} \right\rfloor \bmod n \neq \left\lfloor \frac{C}{w_j} \right\rfloor \bmod n \quad \text{(모든 } 1 \le i < j \le n \text{ 에 대해).}$$

이러한 가장 작은 $C$ 는 항상 $W$ 의 원소 중 적어도 하나의 배수입니다.

유용한 관찰: 어떤 쌍 $i \neq j$ 에 대해 $\left\lfloor \frac{C}{w_i} \right\rfloor \bmod n = \left\lfloor \frac{C}{w_j} \right\rfloor \bmod n$ (충돌)이 성립하면, $C$ 가 적어도

$$\min\left( \left( \left\lfloor \frac{C}{w_i} \right\rfloor + 1 \right) \cdot w_i, ; \left( \left\lfloor \frac{C}{w_j} \right\rfloor + 1 \right) \cdot w_j \right)$$

에 도달하기 전까지는 두 바닥 값 중 어느 것도 바뀌지 않으므로, 그보다 작은 $C$ 로는 이 충돌을 해소할 수 없습니다. 모든 충돌을 해소해야 하므로, 현재의 모든 충돌에 대한 이 한계값들 중 가장 큰 값으로 $C$ 를 건너뛴 뒤 다시 검사하는 것이 효율적입니다.

단어 인코딩. 각 단어를 왼쪽에서 오른쪽으로 글자 단위로 처리하여 숫자로 바꿉니다. 'a'는 1, 'b'는 2, $\ldots$, 'z'는 26으로 두고, 글자마다 5비트를 사용합니다(다음 글자를 더하기 전에 왼쪽으로 5비트 이동, 즉 32를 곱합니다). 따라서 'a' $= 1$, 'bz' $= (2 \cdot 32) + 26 = 90$ 입니다.

입력은 한 줄에 하나씩 주어지는 단어 목록들의 나열이며, 파일 끝(EOF)에서 끝납니다. 각 줄은 소문자 다섯 글자 이하의 단어 2개 이상 13개 이하로 이루어지며, 단어들은 하나 이상의 공백으로 구분됩니다. 각 줄에는 항상 한 글자짜리 단어가 적어도 하나 있습니다.

각 단어 목록마다 입력 줄을 그대로 출력하고, 다음 줄에 그 목록의 해시 함수에 대한 $C$ 값을 출력합니다. 연속한 목록의 답 사이에는 빈 줄을 하나 출력합니다. $C$ 는 항상 부호 있는 32비트 정수 범위에 들어갑니다.