Max's Anger Contest Series 2 P2 - Password Anger

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

After clicking the "Complete Sign-up" button, Max is prompted that his 30-character length password is too long and can only be at most N characters.

Note that passwords can only be lowercase letters.

Max thought

Why do some websites have maximum length requirements for passwords?

Then, he set this problem in anger.

Max found the hash function that this website uses for passwords in C++, Java, and Python:

C++:

int get_hash(string s) {
    int hash = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        hash = hash * 13 + s[i] - 'a' + 1;
    }
    return hash;
}

Java:

static int get_hash(String s) {
    int hash = 0;
    for (int i = 0; i < s.length(); i++) {
        hash = hash * 13 + s.charAt(i) - 'a' + 1;
    }
    return hash;
}

Python:

def get_hash(s):
    hash = 0
    for i in range(len(s)):
        hash = hash * 13 + ord(s[i]) - ord('a') + 1
    return hash

Max figured that if he could count the number of passwords with a length of N that hash to M and inform the website, they would remove the length requirement (and maybe fix their hash functions).

Can you help Max count the number of passwords to convince the website to change this policy?

Constraints

1 \le N \le 4

1 \le M \le 61\,880

Note that passwords can only be lowercase letters.

Input Specification

The first line will contain two integers, N and M, the length of the password and the hash for that password.

Output Specification

Output the number of passwords with a length of N that hash to M based on the above hash functions.

Sample Input 1

1
16

Sample Output 1

1

Sample Input 2

4
32130

Sample Output 2

8

Comments

There are no comments at the moment.