- [USACO 2004 Mar]Lying Livestock 说谎的牲畜
P2923题面缺失
- 2023-2-15 20:42:34 @
题面缺失。原题面如下:
Description
Alphabet consists of initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet is the sum of weights of all letters in this word. A language over an alphabet is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words.
We say that the language is prefixless if for each pair of different words from this language is not a prefix of . We want to find out what is the minimal possible weight of an -element, prefixless language over an alphabet .
Assume that , the weight of the letter a
— and the weight of the letter b
— . Then the weight of the word ab
— . . The weight of the language — . The language is not prefixless, since the word ab
is a prefix of aba
. The lightest tree-element, prefixless language over the alphabet A2 (assuming that weights of the letters are as before) is {b, aa, ab}; its weight is 16.
Write a program that:
reads two integers n, k and the weights of k letters of an alphabet Ak from the standard input; computes the minimal weight of a prefixless, n-element language over the alphabet Ak; writes the result to the standard output. Input In the first line of the standard input there are two positive integers n and k separated by a single space, (2 ≤ n ≤ 10,000, 2 ≤ k ≤ 26). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains k positive integers separated by single spaces. Each of them is not greater than 10,000. The i-th number is the weight of the i-th letter.
Output In the first and only line of the standard output there should be written one integer — the weight of the lightest prefixless n-element language over the alphabet Ak.
Sample Input 1 3 2 2 5 Sample Output 1 16
0 comments
Information
- ID
- 2923
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- (None)
- # Submissions
- 2
- Accepted
- 1
- Uploaded By