Условие

Как правило, идеальных каналов связи на практике не существует, и в любом реальном канале обязательно имеется искажение передаваемых данных. Надежность передачи сообщения достигается через избыточность, и самый простой способ её ввести – передать сообщение несколько раз. 

В представленном коде каждый бит исходного сообщения при передаче повторяется некоторое число раз подряд, и затем в конце сообщения дописываются нули так, чтобы сообщение было представлено байтовой строкой. Она передаётся через канал с помехой, инвертирующей случайные биты.

Ваша задача — декодировать полученный сигнал, восстановив исходное сообщение. Если однозначное декодирование невозможно, сигнал считается повреждённым. Гарантируется, что ложные инверсии блоков отсутствуют, а длина повтора определяется однозначно. Но исходные данные могут быть сформированы некорректно.

Формат входных данных

Последовательность байт произвольной длины. Первый байт – длина исходного сообщения в битах, далее идёт закодированное сообщение.

Формат выходных данных

В случае успешного декодирования — одно целое число, представляющее собой десятичное значение восстановленного двоичного сообщения.

Если сигнал декодировать невозможно — строка `Invalid`.

Для решения этой задачи у вашей команды есть 20 попыток.

Видео-разбор

  

Разбор

В сообщении каждый бит дублируется несколько раз, чтобы помехи не искажали информацию. В конце сообщения, если оно не может быть представлено в виде байтов, добавляются нули, до кратности байту.

Из первого байта узнаём длину исходного сообщения в битах. Зная общую длину полученных данных и количество исходных битов можно вычислить, сколько раз каждый бит повторялся. Если не получается подобрать количество повторов, то данные некорректны.

Далее разбиваем сообщение на блоки нужной длины, каждому блоку присваиваем значение, которое встречается чаще в этом блоке. Если количество разных значений в блоке одинаковое, то восстановить блок невозможно.

Last modified: Friday, 15 May 2026, 7:07 AM