1392_Hashing

Given a hash table of size N, we can define a hash function H(x) = x%N. Suppose that the linear probing is used to solve collisions, we can easily obtain the status of the hash table with a given sequence of input numbers.

However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤ 1000), which is the size of the hash table. The next line contains N integers, separated by a space. A negative integer represents an empty cell in the hash table. It is guaranteed that all the non-negative integers are distinct in the table.

For each test case, print a line that contains the input sequence, with the numbers separated by a space. Notice that there must be no extra space at the end of each line.

11
33 1 13 12 34 38 27 22 32 -1 21

1 13 12 21 33 34 38 27 22 32

采用线性探测法解决冲突，容易建立一个哈希表。哈希函数也很简单：H(x) = x % N，其中N是哈希表的大小。

现在问题是要根据已建好的哈希表，重新构造出输入的关键字序列。为使答案唯一，要求关键字序列字典序最小。

用例解释：

各关键字的哈希值是：

33 % 11 = 0， 1 % 11 = 1， 13 % 11 = 2， 12 % 11 = 1， 34 % 11 = 1， 38 % 11 = 5，

27 % 11 = 5,  22 % 11 = 0， 32 % 11 = 10， 21 % 11 = 10

33放在正确的哈希位置0上，与其有冲突的是关键字22，但22并没有放在位置0，而是放在位置7上。所以22肯定在33后面才输入，而且由于线性探测的原则，22的前面六个位置都被占用，才被迫放在位置7。

1放在正确的哈希位置1上，与其有冲突的关键字有12和34，12的位置比34靠前，根据线性探测原则，所以这三个关键字的相对先后输入顺序是1 - 12 - 34。

13放在正确的哈希位置2上，所以它要早于12，否则，根据线性探测法，12就要占用了位置2。

38放在正确的哈希位置5上，与其有冲突的27却放在38其他位置上，所以38肯定先于27输入。

21放在正确的哈希位置10上，与之有冲突的32却放在其他位置上，所以21肯定先于32输入。另外注意到32是由于后面没有位置存放了，要从头开始找空闲位置，找到位置8。