<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.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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