University of Ulm Local Contest

Source file: elias.(c|cc|hs|java|pas)

Input file: elias.in

The Elias gamma code is a simple code which can be used to encode a sequence of positive integers.
We will use a modified code which is also able to encode zeros.
To encode an integer ** n**, do the following:

- Let
be the number of bits of*k**n* - Write
zeros followed by a*k-1**1* - Write
in binary*n*

Examples | ||||
---|---|---|---|---|

Number | Binary | Number of bits | Prefix | Code |

0 | 0 | 1 | 1 | 10 |

1 | 1 | 1 | 1 | 11 |

2 | 10 | 2 | 01 | 0110 |

3 | 11 | 2 | 01 | 0111 |

4 | 100 | 3 | 001 | 001100 |

5 | 101 | 3 | 001 | 001101 |

6 | 110 | 3 | 001 | 001110 |

7 | 111 | 3 | 001 | 001111 |

8 | 1000 | 4 | 0001 | 00011000 |

A sequence of integers is encoded by writing the codes of the individual integers of the sequence in the same order as the integers appear in the sequence.
The prefix of ** k** additional bits before the binary representation of each integer is needed to
be able to decode the encoded integers. So when reading the encoding of a sequence
of integers, if we read

If we want to shorten the length of the encoding of a sequence of integers, there may be still some room for improvement; we will consider the following two optimizations:

- If there is a prefix which indicates that
bits are following, but there is no integer in the sequence with*k*bits, we can use this prefix to indicate that*k*bits are following. If there already was a prefix which indicates that*k+1*bits are following, this prefix is not needed anymore, and it can be used to indicate that*k+1*bits are following, and so on.*k+2* -
We can add a leading zero to the binary representation of all integers in the sequence with
bits, which then become integers with*k*bits, and then the first optimization can be used. This optimization seems especially useful if there are few integers with*k+1*bits, but many integers with more than*k*bits.*k*

When we are minimizing the length of the encoding of a sequence of integers, we only care about how many integers in the sequence have a certain number of bits. Let ** c_{i}** denote the number of integers in a sequence with

Let us look at the following example:
** c_{1} = 2, c_{2} = 4, c_{3} = 0, c_{4} = 1** (which, for example, could correspond to a sequence

Both optimizations can possibly be used several times. Note that for the second optimization, it is not easy to decide when and how to use it. The goal is to combine these two optimizations in the best possible way, that means we want to find an encoding of a given sequence of integers that has minimum length among all encodings using elias gamma coding with any combination of these two optimizations.

The input file contains several test cases. Each test case starts with a line containing an integer ** n**,
(

For each test case print one line with the minimum length of an encoding of the given input sequence.

4 2 4 0 1 5 9 4 2 4 3 11 44 56 96 26 73 80 77 50 33 16 78 0

24 99 5494