<ПРЕД Задача:
СЛЕД>
Задачу решил 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.
UserDateAttemptTimeCMSC
mishik13 apr 2008C++402.01256 
mishik13 apr 2008C++600.93258 
mishik13 apr 2008C++500.90276 
WsemirZ27 jun 2008Kylix200.52277 
MIKseR29 jan 2009Kylix400.54285 
zloy_mipt20 aug 2008Kylix200.41291 
DAV01 jul 2009FPC800.50296 
WsemirZ27 jun 2008Kylix100.52301 
JohnJones_00110 sep 2006C++100.60313 
dimka21 nov 2006C++602.91315 
Ravent01 sep 2006Kylix400.45317 
tourist29 nov 2007Kylix101.07330 
N1k1tung17 mar 2007Kylix101.16330 
Языки
C++
16
Kylix
10
FPC
4
Java
2
C
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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

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 = 18.207.106.142