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
mishik`13 apr 2008`C++402.01256
mishik`13 apr 2008`C++600.93258
mishik`13 apr 2008`C++500.90276
WsemirZ`27 jun 2008`Kylix200.52277
MIKseR`29 jan 2009`Kylix400.54285
zloy_mipt`20 aug 2008`Kylix200.41291
DAV`01 jul 2009`FPC800.50296
WsemirZ`27 jun 2008`Kylix100.52301
JohnJones_001`10 sep 2006`C++100.60313
dimka`21 nov 2006`C++602.91315
Ravent`01 sep 2006`Kylix400.45317
tourist`29 nov 2007`Kylix101.07330
N1k1tung`17 mar 2007`Kylix101.16330
 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

 © acm.mipt DevGroupThe page was generated in 200ms