PrefixFreeCode | Topcoder Archive

Problem Statement

A prefix-free code of size N which uses K characters is a set of N distinct strings such that

each string of the set contains only characters '0','1', ..., ('0'+K-1)
no string of the set is a prefix of any other string of the set.

The cost of a prefix-free code can be calculated as sum of costs of characters used to write down all strings of the set.
You are given the size of the code N and the costs of using the characters characterCosts. Return the minimal possible cost of a prefix-free code of size N which uses these character costs.

Definition

Class:: PrefixFreeCode
Method:: minCost
Parameters:: int, int[]
Returns:: int
Method signature:: int minCost(int N, int[] characterCosts)
(be sure your method is public)

Constraints

N will be between 2 and 500, inclusive.
characterCosts will contain between 2 and 50 elements, inclusive.
Each element of characterCosts will be between 1 and 100, inclusive.

Examples

```
3
```
```
{1,4}
```
```
Returns: 11
```
The cheapest code of size 3 is {"00","01","1"}.
```
3
```
```
{1,3,5}
```
```
Returns: 9
```
Here exist two cheapest codes - {"0","1","2"} and {"00","01","1"}.

{ 2, 4, 6, 8,10,12,14,16,18,20,
 22,24,26,28,30,32,34,36,38,40,
 42,44,46,48,50,52,54,56,58,60,
 62,64,66,68,70,72,74,76,78,80,
 82,84,86,88,90,92,94,96,98,100}

Returns: 9464

```
500
```
```
{1,2,3,4,5,6,7,8,9,10}
```
```
Returns: 4732
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.