Расстояние Хэмминга

В связи с особенностями линии связи, используемой для передачи сообщений из пункта A в пункт B, каждый бит принятого сообщения с вероятностью 0.001 содержит ошибку.

Из пункта A в пункт B было послано одно из n сообщений m₁, m₂, ..., m_n. В пункте B было принято сообщение s.

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

Расстоянием Хэмминга двух строк a и b одинаковой длины называется количество позиций, в которых эти строки различаются (количество элементов в множестве {i | 1 ≤ i ≤ |a|, a_i ≠ b_i }).

Входные данные

Первая строка входного файла INPUT.TXT содержит s — принятое сообщение. Вторая строка содержит целое число n — количество сообщений, которые могли быть отправлены. Следующие n строк содержат m_i — эти сообщения. Длины всех сообщений равны (|s| = |m₁| = |m₂| = ... = |m_n|). Сообщения непустые, состоят только из символов 0 и 1. Размер входного файла не превосходит 60 Кб.

Выходные данные

В первую строку выходного файла OUTPUT.TXT выведите k — количество сообщений, на которых достигается минимум расстояния Хэмминга. Во вторую строку выведите в порядке возрастания k чисел — номера этих сообщений.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]