哈希冲突
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem: 哈希冲突
时间限制:1s
空间限制:256MB
Background:
通常,中学中形如 的式子为我们所熟知,被称为函数。实际上,设该函数的定义域为集合 ,值域为集合 ,则我们可称该式子为集合 中元素到集合 中元素的一个映射。
定义“离散化”:设存在一组整数,这组整数共有 个整数,而这组数据的极差为 。若 (即 远大于 ),则称这组数据的离散化程度高。反之,则称这组数据的离散化程度低。
在实际应用中,时常会出现这样的情况:存在一组共有 个整数的数据,尽管 很小,即这一组数据的量并不大,但是这一组数据的离散化程度非常高。譬如统计某人的所有网友到他所在地的距离(单位:米),网友的数量 可能并不大,但是若要统计到此人距离为 的人数时,我们不能开一个大小达到 (即 )的数组,因为这会造成严重的空间浪费,是我们所不能接受的。这时候,我们就需要一个映射 ,使得对于每一个距离 ,经过映射后的值控制在 附近,并且对于不同的 ,他们映射的值不一样。此时,这样的从原距离的集合到新的集合的映射被我们称为哈希函数。
然而,最终的结果常常事与愿违。由于数据的随机性,经过哈希函数的映射后,可能会存在两个不同的距离 ,使得 ,此时,我们称 这两个数产生了哈希冲突。
现在,原力清理大师对此非常感兴趣,并找了一组数据,创建了一个哈希函数做映射,以更深入地了解哈希函数的奥义。这组数据由 个整数组成,每个数的范围都在 到 之间(太大了原力清理大师怕自己做不出来 )。设原数组为数组 ,原力清理大师希望将原来的数组通过自定义的哈希函数 ,按照下标从小到大的顺序,映射到另一个新的长度为 的数组 中,其中哈希函数 为 ,即 为 映射到数组 中的下标。很明显,由于原力清理大师的火候不够,原数组经过映射后将会产生大量的哈希冲突。原力清理大师相当恼火,希望你能告诉他会产生多少次哈希冲突,即存在多少个不同的 ,使得 ,函数 的定义见上文。同时,原力清理大师还希望你给出最终的 数组,其中,数组未被赋值的位置默认为 ,产生哈希冲突的位置取两个数的平均数。最终结果均保留六位小数( 除外)。
Input Format
第一行一个整数 ,代表数组的长度。
第二行共 个整数,代表数组中 的值 ,未被赋值则默认为 。
Output Format
第一行输出一个整数,代表新数组中哈希冲突的数量。
第二行输出 个数,代表经过映射后新数组中每一位的值,输出结果保留六位小数。
Input Example1:
4
1 2 0 3
Output Example1:
0
2.000000 0.000000 1.000000 3.000000
Input Example2:
4
3 1 0 1
Output Example2:
1
2.000000 2.000000 -1.000000 0.000000
Explanation:
样例一中, ,不存在哈希冲突,故为 。
样例二中, ,又出现了 ,产生哈希冲突,取平均得到 。
对于 的数据,满足 (含义见题目描述), 。