Hashing
Ao trabalhar com coleções de elementos, como uma lista de strings ou uma lista de tuples, acaba por ser muito dispendioso, em termos de recursos computacionais, pesquisar elementos dentro da coleção ou responder a perguntas como “O item X está presente na nossa coleção?”. No entanto, comparar números é muito mais rápido, e os nossos computadores são altamente otimizados para fazer comparações numéricas (diferentemente de strings ou tuples). Assim, se conseguirmos mapear os dados para um valor numérico, certas operações como encontrar um item ou verificar a sua existência na coleção tornam-se mais eficientes.
A técnica de mapear dados de tamanho arbitrário para dados de tamanho fixo chama-se hashing. O número resultante (hash) funciona como um identificador único dos dados originais. Geralmente, dispõe-se de uma função
hash que consegue mapear os dados iniciais para um valor de tamanho fixo (como um número).No Python, por exemplo, existe a função integrada
hash, que converte qualquer objeto imutável num número, normalmente no intervalo . Note que esta função só pode mapear objetos imutáveis: se tentarmos fazer hash de uma lista ou de um dicionário (que são mutáveis e podem ser alterados adicionando ou removendo elementos), vamos obter um erro:print(hash(123)) # 123
print(hash('Anna')) # 2573300035916889866
print(hash('Bob')) # -2781086332262035333
print(hash((2, 'Simon'))) # -6551767300073204554
print(hash([1, 2])) # TypeError: unhashable type: 'list'Desafio: Criar hash para um par de inteiros
Vamos implementar uma função hash personalizada, chamada
h. Ela vai receber um par de inteiros e deve devolver o valor de hash resultante. A função h define-se da seguinte forma:Isto garante que o valor de hash fica sempre no intervalo [0; 5077).
Entrada
A única linha da entrada contém dois números
a e b ( ≤ a, b ≤ ).Saída
O programa deve imprimir o hash do par (a, b).
Exemplos
Input | Output |
4 5 | 2916 |
23452 5432 | 3751 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB