Условие

Задача является прямым продолжением задачи «Честный сигнал»

Так, двоичное сообщение было закодировано с помощью кода Хэмминга. Исходное сообщение было разделено на неравные блоки фиксированной длины, после чего каждый блок был независимо закодирован. Длины этих блоков заранее неизвестны. Но точно известно, что в процессе передачи данных ошибок не возникло.

...подождите, что-то здесь не так.

Перед кодированием сообщение было разделено на блоки, причём их длина могла быть разной (от 7 до 31 бита). После передачи длины блоков, и как следствие границы между ними, были утеряны. Ваша задача — восстановить исходное сообщение.

...а мы точно уверены, что оно декодируется однозначно?

Нет, поэтому нужно найти все возможные варианты исходного сообщения.

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

Одна строка, состоящая из символов '0' и '1' — шифротекст.

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

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

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

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

 

Разбор

Блоки в этой задаче могут быть разной длины, где между ними границы - неизвестно. Нужно найти все возможные способы разбить строку на валидные блоки хэмминга.

Идем с начала строки, пробуем отделить блок. Для каждого варианта проверяем, является ли блок корректным кодом. Если да, то рекурсивно обрабатываем остатки строки. Если дошли до конца строки, то нашли один из ответов.

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

Last modified: Friday, 15 May 2026, 5:59 AM