DMOPC '19 Contest 3 P2 - Generating Names

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

Veshy is trying to come up with a username for his new alt-account! Unfortunately, he is currently in a creative lull, so he has turned to permuting strings of lowercase letters of length N to find a username. This was still not creative enough for Veshy, so he is currently trying to increase the number of potential candidate usernames by having K wildcard characters (*) in his starting string before permuting. Since you are Veshy's absolute best friend, help him find the number of candidate usernames!


For all subtasks:

1 \le N \le 15

0 \le K \le 2

Subtask 1 [10%]

N \le 5

Subtask 2 [10%]

K = 0

Subtask 3 [20%]

K = 1

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line will have 2 space-separated integers, N and K. The following line will have a string composed of only lowercase alphabet characters and/or the character *. There will be K *'s in the string.

Output Specification

Output the total number of possible permutations of the string.

Sample Input 1

2 1

Sample Output 1


Explanation of Sample Output 1

There are 26 different possibilities for the wildcard character. Out of these 26 possibilities, 25 result in 2 unique permutations (e.g. baba and ab, bcbc and cb, etc.), and 1 results in only 1 unique permutation (when the wildcard character is b, to make bb). 2 \times 25 + 1 = 51.

Sample Input 2

2 2

Sample Output 2



There are no comments at the moment.