P2168 [NOI2015] Homer’s Epic

> He who chases a shadow is himself a shadow —— Homer.

Allison has recently become obsessed with literature. On a lazy afternoon, she likes to slowly sip a cappuccino and quietly read her beloved Homer’s Epic. However, the grand work composed of The Odyssey and The Iliad is just too long, so Allison wants to shorten it by using an encoding method. In one Homer’s Epic, there are $n$ distinct words, numbered from $1$ to $n$. The total number of occurrences of the $i$-th word is $w_i$. Allison wants to replace the $i$-th word with a base-$k$ string $s_i$ such that the following condition holds: For any $1 \leq i, j \leq n$, $i \ne j$, we have: $s_i$ is not a prefix of $s_j$. Now Allison wants to know how to choose $s_i$ to minimize the length of the new Homer’s Epic after replacement. Among all choices that minimize the total length, she also wants to know the minimal possible value of the maximum length among all $s_i$. A string is called a base-$k$ string if and only if each of its characters is an integer between $0$ and $k-1$ inclusive. A string $str1$ is called a prefix of a string $str2$ if and only if there exists $1 \leq t \leq m$ such that $str1 = str2[1..t]$. Here, $m$ is the length of $str2$, and $str2[1..t]$ denotes the string consisting of the first $t$ characters of $str2$.

The first line contains $2$ positive integers $n, k$, separated by a single space, indicating that there are $n$ types of words and base-$k$ strings are to be used for replacement. The next $n$ lines: the $(i+1)$-th line contains $1$ positive integer $w_i$, indicating the number of occurrences of the $i$-th word.

Output consists of $2$ lines. The first line contains $1$ integer, the minimal total length of Homer’s Epic after re-encoding. The second line contains $1$ integer, the minimal possible value of the maximum length among all $s_i$ under the condition that the total length is minimized.

Sample Explanation Sample 1 explanation Let $X(k)$ denote that $X$ is a base-$k$ string. One optimal scheme: let $00(2)$ replace the $1$-st word, $01(2)$ replace the $2$-nd word, $10(2)$ replace the $3$-rd word, and $11(2)$ replace the $4$-th word. Under this scheme, the minimal encoded length is: $$1 × 2 + 1 × 2 + 2 × 2 + 2 × 2 = 12$$ The maximum length of $s_i$ is $2$. A non-optimal scheme: let $000(2)$ replace the $1$-st word, $001(2)$ replace the $2$-nd word, $01(2)$ replace the $3$-rd word, and $1(2)$ replace the $4$-th word. Under this scheme, the minimal encoded length is: $$1 × 3 + 1 × 3 + 2 × 2 + 2 × 1 = 12$$ The maximum length of $s_i$ is $3$. Compared with the optimal scheme, the article length is the same, but the maximum codeword length is larger. Sample 2 explanation One optimal scheme: let $000(3)$ replace the $1$-st word, $001(3)$ replace the $2$-nd word, $01(3)$ replace the $3$-rd word, $02(3)$ replace the $4$-th word, $1(3)$ replace the $5$-th word, and $2(3)$ replace the $6$-th word. Constraints All testdata ranges and characteristics are as follows (all data satisfy $0 < w_i \leq 10^{11}$): | Test No. | Scale of $n$ | Scale of $k$ | Remarks | | :------: | :-----------: | :----------: | :-----: | | $1$ | $n=3$ | $k=2$ | | | $2$ | $n=5$ | ^ | ^ | | $3$ | $n=16$ | ^ | All $w_i$ are equal | | $4$ | $n=1\,000$ | ^ | $w_i$ are uniformly random within the range | | $5$ | ^ | ^ | | | $6$ | $n=100\,000$ | ^ | ^ | | $7$ | ^ | ^ | All $w_i$ are equal | | $8$ | ^ | ^ | | | $9$ | $n=7$ | $k=3$ | ^ | | $10$ | $n=16$ | ^ | All $w_i$ are equal | | $11$ | $n=1\,001$ | ^ | ^ | | $12$ | $n=99\,999$ | $k=4$ | ^ | | $13$ | $n=100\,000$ | ^ | ^ | | $14$ | ^ | ^ | ^ | | $15$ | $n=1\,000$ | $k=5$ | ^ | | $16$ | $n=100\,000$ | $k=7$ | $w_i$ are uniformly random within the range | | $17$ | ^ | ^ | | | $18$ | ^ | $k=8$ | $w_i$ are uniformly random within the range | | $19$ | ^ | $k=9$ | | | $20$ | ^ | ^ | ^ | Additional Tips Contestants should use 64-bit integers for input, output, storage, and computation. Scoring For each test point: - If the first line of the output is correct, you will receive $40\%$ of the score for that test point. - If the entire output is correct, you will receive $100\%$ of the score. Translated by ChatGPT 5