Hashing
Wenn man mit Sammlungen von Elementen arbeitet, zum Beispiel mit einer Liste von Strings oder einer Liste von Tupeln, kann es sehr rechenintensiv werden, nach bestimmten Elementen zu suchen oder Fragen wie „Ist das Element X in unserer Sammlung vorhanden?“ zu beantworten. Der direkte Vergleich von Zahlen ist jedoch sehr schnell, und Computer sind darauf spezialisiert, Zahlen äußerst effizient zu vergleichen (im Gegensatz zu Strings oder Tupeln). Daher kann es sinnvoll sein, unsere Daten in eine Zahl umzuwandeln, um Operationen wie das Auffinden oder das Überprüfen des Vorhandenseins eines Elements in der Sammlung zu beschleunigen.
Die Methode, Daten beliebiger Größe in Daten einer festen Größe abzubilden, nennt man Hashing. Die resultierende Zahl (der Hash) dient dann als eindeutige Kennung der ursprünglichen Daten. Meistens steht uns eine
hash-Funktion zur Verfügung, die die ursprünglichen Daten in ein Ergebnis fester Größe (etwa eine Zahl) überführt.In Python gibt es beispielsweise eine eingebaute
hash-Funktion, die jedes unveränderliche Objekt in eine Zahl abbilden kann, die normalerweise im Bereich liegt. Nur unveränderliche Objekte können gehasht werden. Versucht man, eine Liste oder ein Dictionary (die veränderlich sind und durch Hinzufügen oder Entfernen von Elementen geändert werden können) zu hashen, führt das zu einem Fehler: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'Challenge: Hash a pair of integers
Lass uns eine eigene Hash-Funktion
h implementieren. Diese Funktion erhält ein Zahlenpaar und soll den entsprechenden Hash-Wert ausgeben. Die Funktion h ist wie folgt definiert:Damit wird sichergestellt, dass der Hash-Wert immer im Bereich [0; 5077) liegt.
Eingabe
Die einzige Zeile der Eingabe enthält zwei Zahlen
a und b ( ≤ a, b ≤ ).Ausgabe
Das Programm soll den Hash des Paares (a, b) ausgeben.
Beispiele
Eingabe | Ausgabe |
4 5 | 2916 |
23452 5432 | 3751 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB