<PREV Problem:
NEXT>
Solved by 31 users: 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 
Languages
C++
16
Kylix
10
FPC
4
Java
2
C
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Clusterization of binary words

Time limit = 5 seconds

You are given a set of binary words of fixed length. The problem is to form the minimal possible number of groups while the Hamming distance between the words from the same group does not exceed D. Hamming distance between two words is the number of places, where the words do not coincide.

You do not have to find the optimal subsets, but your solution should be quite optimal. The number of clusters in your solution should not exceed some critical number. Generally, the value is equal to 1.25 * (optimal number of clusters).

Input First line contains 3 integers: N — number of words, L — length of the word, D — maximal distance for a group, 0 < N < 1000, 0 < L < 256, 0 < D < L. Then follow N lines with N words of '0' or '1'.

Output First line: number of clusters. Next lines should describe the clusters (the list of numbers of all the words in it). The first word in input is numbered with 1.

Input#1
5 5 2
11111
00000
11110
00001
11111
Output#1
2
1 3 5
2 4

Author:
folklore, description and tests by Dmitry Polishchuk
25 april 2005

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 18.232.133.231