|Online MIPT programming contest||РУССКИЙ|
Time limit = 5 secondsYou 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.
5 5 2 11111 00000 11110 00001 11111
2 1 3 5 2 4
folklore, description and tests by Dmitry Polishchuk
25 april 2005
© acm.mipt DevGroup
The page was generated in 180ms