Man in the middle
Time limit2sMemory limit512 MB
Find the lexicographically smallest uppercase string of length L whose polynomial hash mod 10007 equals H, or report that none exists.
- Level
Medium6 of 10
- Topics
- Math, Number theory, Greedy, Dynamic programming
- Solved
- No attempts yet
Problem
Alice and Bob are good friends who trust each other even though they live in different countries. One day Bob had an idea for a startup that will change the world, but he needed funds. Alice agreed to give him the money he needs. Since Bob does not have a bank account, Alice told him she will transfer the money to her friend Eve, who lives in the same city as Bob, and all he needs to do is tell Eve the secret code and she will hand him the money.
Because they were communicating over the internet, Alice was worried that someone might be spying on their conversation and could hear the secret code. Bob is one of the brightest people Alice has met, so she decided to tell Bob the code after it was hashed by a certain function, and she knows that if someone else was listening to their conversation, Bob will still manage to figure out the secret code first. Bob knows the following about the code:
- The code has length L.
- The code is formed only of the letters ‘A’..‘Z’ (uppercase only).
- The formula used to calculate the hash: [\left(\left( \sum_{i=1}^{L-1}{n_i \times M^{L-i}} \right) + n_L \right) \mod {10007}]
- n_i is the numerical value that represents the letter at index i (1 ≤ i ≤ L), where A = 0, B = 1, C = 2, . . . , Z = 25.
- The code is the lexicographically least string formed of the letters ‘A’..‘Z’ that hashes to a given value H using the function above.
Can you help Bob figure out the secret code quickly before someone else figures it out?
Input
Your program will be tested on one or more test cases. The first line of the input contains a single integer T, the number of test cases. (1 ≤ T ≤ 100)
Each test case consists of one line containing three space-separated integers:
- L: the length of the secret code (1 ≤ L ≤ 100, 000)
- H: the hash value of the code (0 ≤ H < 10, 007)
- M: the multiplier used in the hash formula (0 ≤ M ≤ 20)
Output
For each test case, print a single line containing the secret code if it is possible to find such a string, or ‘None’ if there is not one (the quotes are for clarity).