DMOPC '19 Contest 3 P2 - Generating Names

View as PDF

Submit solution

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

Authors:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 permutating 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 permutating. Since you are Veshy's absolute best friend, help him find the number of candidate usernames!

Constraints

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
b*

Sample Output 1

51

Sample Input 2

2 2
**

Sample Output 2

676

Explanation of Sample Input 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.


Comments

There are no comments at the moment.