IF672 - Algoritmos e Estruturas de Dados
novembro 2002 a março 2003

2 - Função Hashing trivial generalizada

  

Considere uma seqüência s0s1s2...sn de dígitos. 
Essa questão tem como objetivo principal a indexação direta dessas seqüências.
O problema é encontrar um função Hashing para essas seqüências de tal forma que,
Se duas string s1 e s2, forem tais que s1 < s2, então f(s1) < f(s2).
Ou seja:
     f(0000) = 0, f(0001) = 1, f(0010) = 2, etc... para dígitos 0 e 1.
     f(0000) = 0, f(0001) = 1, f(0002) = 2, etc... para dígitos 0..2.
     ...
     f(000A) = 10, f(000B) = 11, f(000C) = 12, etc... para dígitos de 0..F
       


Entrada e Saída de dados

A entrada consiste em várias linhas.
Para cada linha teremos dois inteiros N, K e uma seqüência Si com N dígitos (na base K).
O fim de do arquivo corresponde ao final da entrada.

A saída consiste de um valor F(Si) (< Maior Inteiro) para cada linha da entrada.

Entrada exemplo

 
7 2 0000101

4 2 1100

4 2 1110

4 2 0010

5 2 11111

6 2 111111

6 2 001101

1 2 0

1 2 1

1 3 1

4 3 0002

4 16 000F

Saída correspondente

5

12

14

2

31

63

13

0

1

1

2

15