6 - Hotel e Hashing

Hilbert, grande matemático de todos os tempos, mostrou uma maneira intuitiva de "ver" o infinito.
Considere que se tem um hotel com quartos infinitos, todos cheios. Agora imagine que infinitos turistas vêm em um ônibus
com capacidade infinita. Como faríamos para alojá-los no hotel? 
Todo mundo que estivesse no quarto N iria pro quarto 2*N, e agora teriamos infinito espaços para colocar infinitas pessoas.
(Isso seria possível se esse infinito tivesse a mesma cardinalidade dos números naturais)
Para esse problema usaremos essa idéia, mas em um "hotel" finito.
Clientes serão indexados em um quarto do hotel dependendo de seu CPF (tem 5 dígitos).
O hotel no começo tem 57 quartos. A função hashing inicialmente é f(CPF) = (CPF + 23) %  57.
Se houver colisão, o hotel terá seu número de quartos duplicado, e a função será modificada.
A função terá dois parâmetros f(CPF, n) onde n é o número de colisão.
Para esse problema não haverá rearrumação dos clientes nos quartos do hotel, pois os mesmo não são
tão "mente aberta" quanto os de Hilbert.


Na Prática

F(CPF, n) = ((3^n) * CPF + 23) % ((2^n) * 57).
Cada vez que acontecer colisão atualizar n e F, achar o outro valor de F(CPF,n).
Essa função pode não ser adeqüada para todos as entradas, por isso se 57 * 2^n ficar maior que 
1.000.000 (maior número de quarto no hotel) o processo deve ser parado.
Use long de JAVA e não int. (quem usar C/C++ use __int64 no windows ou long long no linux).
Ao invés de multiplicar o array comece implementando isso com um array de tamanho 1.000.000,
quando tiver que duplicar apenas use a função que ela já trata isso.
(Note que em uma situação real o array realmente seria duplicado)

Entrada e Saída de dados

A entrada será vários CPF's de cliente.
A saída será: para cada CPF informar onde ele foi inserido, e quantas colisões houveram a mais após a inserção.

Note que para saber onde se encontra um dado CPF, mesmo após fazer várias iterações do algoritmo, basta manter um array
com a função inversa.. dado um CPF, achar o cliente no array, ou seja seu índice. Mas isso não será cobrado nessa questão.

Entrada exemplo

00000
00001
00002
00020
00057
00114
00050
00100
01010
12001
20010
20111
10112
13212
99999
56572
00011
00017
11001
10113
32214
56446
89448
28791
67682
18623
19152
73737
68585
00016
00005
00102
02439
00356
00143
00116
00803
01808
01607
00518
00519
01000
10010
01001

Saída correspondente

posicao: 23  -  colisoes adicionais: 0
posicao: 24  -  colisoes adicionais: 0
posicao: 25  -  colisoes adicionais: 0
posicao: 43  -  colisoes adicionais: 0
posicao: 80  -  colisoes adicionais: 1
posicao: 137  -  colisoes adicionais: 1
posicao: 17  -  colisoes adicionais: 0
posicao: 11  -  colisoes adicionais: 0
posicao: 221  -  colisoes adicionais: 0
posicao: 188  -  colisoes adicionais: 0
posicao: 389  -  colisoes adicionais: 1
posicao: 380  -  colisoes adicionais: 0
posicao: 359  -  colisoes adicionais: 0
posicao: 155  -  colisoes adicionais: 0
posicao: 20  -  colisoes adicionais: 0
posicao: 323  -  colisoes adicionais: 0
posicao: 320  -  colisoes adicionais: 0
posicao: 26  -  colisoes adicionais: 0
posicao: 194  -  colisoes adicionais: 0
posicao: 386  -  colisoes adicionais: 0
posicao: 209  -  colisoes adicionais: 0
posicao: 113  -  colisoes adicionais: 0
posicao: 143  -  colisoes adicionais: 0
posicao: 356  -  colisoes adicionais: 0
posicao: 245  -  colisoes adicionais: 0
posicao: 332  -  colisoes adicionais: 0
posicao: 935  -  colisoes adicionais: 2
posicao: 962  -  colisoes adicionais: 0
posicao: 290  -  colisoes adicionais: 0
posicao: 263  -  colisoes adicionais: 0
posicao: 1238  -  colisoes adicionais: 0
posicao: 1097  -  colisoes adicionais: 0
posicao: 1724  -  colisoes adicionais: 0
posicao: 803  -  colisoes adicionais: 0
posicao: 116  -  colisoes adicionais: 0
posicao: 851  -  colisoes adicionais: 0
posicao: 1808  -  colisoes adicionais: 0
posicao: 1607  -  colisoes adicionais: 0
posicao: 518  -  colisoes adicionais: 1
posicao: 1901  -  colisoes adicionais: 0
posicao: 2630  -  colisoes adicionais: 0
posicao: 3071  -  colisoes adicionais: 0
posicao: 1313  -  colisoes adicionais: 0
posicao: 152  -  colisoes adicionais: 0