| Автор: | А. Баранов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 2 Мб | |
| Выходной файл: | output.txt |
В рамках одного научно-исследовательского проекта возникла необходимость в эффективной передаче экспериментальных данных, имеющих специальный вид, между различными узлами вычислительной сети. В связи с этим была сформулирована следующая задача.
Пусть имеется некоторая бинарная последовательность (состоящая из нулей и единиц), разбитая на блоки фиксированной длины. При этом заранее известно, что каждый такой блок содержит в себе ровно n нулей и m единиц.
При передаче указанной последовательности по внешнему каналу связи требуется представить ее в сжатом виде. Для этого рассмотрим множество всех различных значений, которые могут принимать составляющие ее блоки. Отсортировав их в лексикографическом порядке, получим некоторый упорядоченный алфавит. Далее заменим каждый отдельный блок входной последовательности числовым кодом, указывающим его позицию в таком алфавите (будем полагать, что нумерация символов алфавита начинается с нуля).
Несложно показать, что размер полученного алфавита обратно пропорционален значению |n − m|. Так, в предельном случае, когда n (или m) равно нулю, алфавит будет состоять всего-лишь из одного символа. В свою очередь, чем меньше размер алфавита, тем меньшее число бит будет требоваться для представления номеров содержащихся в нем символов.
Если предположить, что во входной последовательности преобладают нулевые (либо единичные) биты, тогда от предложенного подхода можно будет ожидать достаточно высокой степени сжатия.
В первой строке входного файла "input.txt" записаны два целых неотрицательных числа n и m. Далее следует текстовая строка, состоящая из n нулей и m единиц.
Выходной файл "output.txt" должен содержать результирующий код указанной строки, представленный в двоичной системе счисления (ведущие нули при этом можно опустить).
0 < (n + m) ≤ 2 ⋅ 104
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|