TheDictionary
SRM 428 · 2008-12-01 · by Vasyl[alphacom]
Problem Statement
John and Brus are studying string theory at the university. Brus has finished his special project - a dictionary that contains all strings of a special type. Each string in his dictionary contains exactly n occurrences of the lowercase letter 'a', m occurrences of the lowercase letter 'z', and no other letters. The strings are listed in alphabetical order.
Your task is to help John by finding the k-th (1-based) string in Brus's dictionary. If there are less than k strings in the dictionary, return an empty String instead.
Constraints
- n will be between 1 and 100, inclusive.
- m will be between 1 and 100, inclusive.
- k will be between 1 and 1,000,000,000 inclusive.
2 2 2 Returns: "azaz"
There are six strings in the dictionary and the second one is "azaz".
2 2 6 Returns: "zzaa"
This string is the last one in the dictionary.
10 10 1000000000 Returns: ""
There are less than k strings in the dictionary.
7 4 47 Returns: "aaazazaazaz"
100 100 1000000000 Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzazzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzazzzzzazzzzzzzzzzzzazzzz"
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheDictionary with a public method string find(int n, int m, int k) · 51 test cases · 2 s / 256 MB per case