<ПРЕД Задача:
СЛЕД>
Задачу решил 31 пользователь: TPH, DD, Jarovit, bloodmage, wojtekt, tomek, Ravent, JohnJones_001, Dmitry_Gozman, dimka, N1k1tung, maciejk, toshiba2, dan, andyzh1314, tourist, mishik, vi002, WsemirZ, zloy_mipt, mazahaka, MIKseR, UdH-WiNGeR, defrager, DAV, RAVEman, Bezier89, ZhanibekDATBAEV, Dest, Robert_Gerbicz, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Кластеризация бинарных слов

Time limit = 5 секунд

Дано множество двоичных слов фиксированной длины. Требуется разбить их на как можно меньшее число кластеров (непересекающихся подмножеств) так, чтобы расстояние между словами в кластере не превышало заданного числа D. Расстояние между словами это количество несовпадающих бит.

Не требуется найти минимум числа кластеров. Нужно чтобы их число было не больше, чем определённое критическое значение. Большинство критических значений в тестовых примерах вычислено как 1.25 * (минимум числа кластеров).

Вход В первой строке дано 3 натуральных числа: N — количество слов, L — длина слова, D — максимальное расстояние, 0 < N < 1000, 0 < L < 256, 0 < D < L. Далее следуют N строк, в каждой из которых находится слово длины L, состоящее из символов '0' или '1'.

Выход В первой строке количество кластеров K. В следующих K строках — номера слов входящих в кластер (слова нумеруются с единицы в порядке входа).

Вход#1
5 5 2
11111
00000
11110
00001
11111
Выход#1
2
1 3 5
2 4

Автор:
фольклор, тесты и описание Дмитрий Полищук
25 апреля 2005

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.219.167.194