Алиса решила написать генератор простых текстов на английском языке. Для хранения текста в памяти она решила использовать неравномерное кодирование, основываясь на частоте букв в английском алфавите. Она воспользовалась простой таблицей:
| Буква |
E |
T |
A |
O |
I |
N |
S |
H |
R |
D |
L |
C |
U |
| Частотность, % |
12.7 |
9.06 |
8.17 |
7.51 |
6.97 |
6.75 |
6.33 |
6.09 |
5.99 |
4.25 |
4.03 |
2.78 |
2.76 |
| Буква |
M |
W |
F |
G |
Y |
P |
B |
V |
K |
X |
J |
Q |
Z |
| Частотность, % |
2.41 |
2.36 |
2.23 |
2.02 |
1.97 |
1.93 |
1.49 |
0.98 |
0.77 |
0.15 |
0.15 |
0.10 |
0.05 |
Кодирование Алисы построено следующим образом:
1. В начале каждого кода символа находится специальный бит, обозначающий начало кода.
2. Затем идёт бит, отвечающий за то, является ли буква заглавной.
3. Кодом длиной i бит она кодирует 2i букв с наибольшей популярностью, которым ещё не назначены более короткие коды. Например, буквы E и T получат однобитные коды, следующие 4 буквы – двухбитные коды, и так далее.
Её друг Боб справедливо заметил, что так как она генерирует простые тексты, в них используется не более 1500 различных слов (Боб также игнорирует регистр букв в слове) и предложил использовать минимальное, одинаковое для всех слов количество бит, а также для каждого слова записывать 1 бит метаинформации – начинается ли слово с заглавной буквы. 54
Определите, при какой минимальной средней длине слова способ Боба будет эффективнее способа Алисы (для хранения всего текста потребуется строго меньше бит). Средней длиной слова будем считать количество символов, поделенное на количество слов и округлённое до ближайшего целого числа. В ответ запишите одно число – искомую среднюю длину