NOI '15 P4 - Homeric Epics - DMOJ: Modern Online Judge

NOI '15 P4 - Homeric Epics

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

In Homeric Epics there are $n$ $n$ different words numbered from $1$ $1$ to $n$ $n$ . The $i$ $i$ -th word appears $w_i$ $w_{i}$ times in the text. Allison wants to substitute the $i$ $i$ -th word with a $k$ $k$ -ary string $s_i$ $s_{i}$ , satisfying the following constraint: for any $1 \le i,j \le n$ $1 \leq i, j \leq n$ , $i \ne j$ $i \neq j$ , $s_i$ $s_{i}$ is not the prefix of $s_j$ $s_{j}$ .

Allison wants to know how to choose $s_i$ $s_{i}$ so that the resulting text has minimum length. Under the assumption that the total length of the text is minimal, Allison wants to know what is the shortest possible length of the longest $s_i$ $s_{i}$ .

A string is called a $k$ $k$ -ary string if and only if its characters are in $\{0, 1, \dots, k-1\}$ ${0, 1, \dots, k - 1}$ .

A string $s_1$ $s_{1}$ is said to be a prefix of $s_2$ $s_{2}$ if and only if there exists $1 \le t \le m$ $1 \leq t \leq m$ such that $s_1 = s_2[1 \dots t]$ $s_{1} = s_{2} [1 \dots t]$ where $m$ $m$ is the length of $s_2$ $s_{2}$ and $s_2[1 \dots t]$ $s_{2} [1 \dots t]$ represents the substring of $s_2$ $s_{2}$ formed by the first $t$ $t$ characters.

Input Specification

The first line of the input file contains two integers $n,k$ $n, k$ separated by one space, denoting there are $n$ $n$ words in total and we need to substitute the words with a $k$ $k$ -ary string.

In the following $n$ $n$ lines, the $(i+1)$ $(i + 1)$ -th line has a nonnegative integer $w_i$ $w_{i}$ denoting the number of times the $i$ $i$ -th word has occurred.

Output Specification

The output consists of two lines. The first line is an integer denoting the minimum length of the Homeric Epics after substitution. The second line is an integer denoting the minimum length of the longest string $s_i$ $s_{i}$ given the total length is minimum.

Sample Input 1

Copy

Sample Output 1

Copy

12
2

Sample Input 2

Copy

Sample Output 2

Copy

36
3

Constraints

Test Case	$n$ $n$	$k$ $k$	Additional Constraints	$w_i$ $w_{i}$
1	$n=3$ $n = 3$	$k=2$ $k = 2$		$0 < w_i \le 10^{11}$ $0 < w_{i} \leq 10^{11}$
2	$n=5$ $n = 5$	$k=2$ $k = 2$
3	$n=16$ $n = 16$	$k=2$ $k = 2$	All $w_i$ $w_{i}$ are equal.
4	$n=1000$ $n = 1000$	$k=2$ $k = 2$	The $w_i$ $w_{i}$ are generated uniformly at random.
5	$n=1000$ $n = 1000$	$k=2$ $k = 2$
6	$n=100\,000$ $n = 100 000$	$k=2$ $k = 2$
7	$n=100\,000$ $n = 100 000$	$k=2$ $k = 2$	All $w_i$ $w_{i}$ are equal.
8	$n=100\,000$ $n = 100 000$	$k=2$ $k = 2$
9	$n=7$ $n = 7$	$k=3$ $k = 3$
10	$n=16$ $n = 16$	$k=3$ $k = 3$	All $w_i$ $w_{i}$ are equal.
11	$n=1001$ $n = 1001$	$k=3$ $k = 3$	All $w_i$ $w_{i}$ are equal.
12	$n=99\,999$ $n = 99 999$	$k=4$ $k = 4$	All $w_i$ $w_{i}$ are equal.
13	$n=100\,000$ $n = 100 000$	$k=4$ $k = 4$
14	$n=100\,000$ $n = 100 000$	$k=4$ $k = 4$
15	$n=1000$ $n = 1000$	$k=5$ $k = 5$
16	$n=100\,000$ $n = 100 000$	$k=7$ $k = 7$	The $w_i$ $w_{i}$ are generated uniformly at random.
17	$n=100\,000$ $n = 100 000$	$k=7$ $k = 7$
18	$n=100\,000$ $n = 100 000$	$k=8$ $k = 8$	The $w_i$ $w_{i}$ are generated uniformly at random.
19	$n=100\,000$ $n = 100 000$	$k=9$ $k = 9$
20	$n=100\,000$ $n = 100 000$	$k=9$ $k = 9$