Хеширование
Когда мы работаем с наборами элементов, такими как список строк или список кортежей, поиск нужного элемента в коллекции или проверка, существует ли элемент X в коллекции, может стать вычислительно дорогой операцией. В то же время, сравнение чисел выполняется очень быстро, и современные компьютеры особенно хорошо оптимизированы под такие сравнения (в отличие от сравнения строк или кортежей). Следовательно, если мы сможем сопоставить наши данные с каким-то числовым значением, то операции поиска или проверки наличия элемента могут стать эффективнее.
Техника преобразования данных произвольного размера в данные фиксированного размера называется хешированием. Полученное при этом число (хеш) выполняет роль уникального идентификатора для исходных данных. Обычно у нас есть функция
hash, способная сопоставлять исходные данные с числом фиксированного диапазона.В Python, например, есть встроенная функция
hash, которая может преобразовывать любой неизменяемый объект в число, обычно лежащее в диапазоне . Отметим, что хешировать можно только неизменяемые объекты. Поэтому, если попытаться вычислить хеш для списка или словаря (которые являются изменяемыми, так как их можно модифицировать), то возникнет ошибка: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'Задача: хеширование пары целых чисел
Реализуем собственную функцию хеширования
h. Она принимает на вход пару целых чисел и должна возвращать их хеш-значение. Функция h определяется следующим образом:Благодаря этому результат всегда будет находиться в диапазоне [0; 5077).
Входные данные
В единственной строке входных данных содержатся два числа
a и b ( ≤ a, b ≤ ).Выходные данные
Программа должна вывести хеш пары (a, b).
Примеры
Входные данные | Выходные данные |
4 5 | 2916 |
23452 5432 | 3751 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB