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.
Definition
- Class:
- TheDictionary
- Method:
- find
- Parameters:
- int, int, int
- Returns:
- String
- Method signature:
- String find(int n, int m, int k)
- (be sure your method is public)
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.
Examples
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"
1
100
100
Returns: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzaz"
1
100
101
Returns: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzza"
100
1
102
Returns: ""
100
1
1000000000
Returns: ""
10
10
184756
Returns: "zzzzzzzzzzaaaaaaaaaa"
48
1
301413357
Returns: ""
25
69
160567226
Returns: "aaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzazazzzzzazzzzzzzzazzazzzzzzzzzzzzzz"
88
52
35766291
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzazzzzzzzzazzzzzzzazzzzzzzaazzazzzzzzzzzzzz"
73
65
597007
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzzazzazzzzzzzzzzzzzzzzzzzzzzzazazzzzzzzzzzzzzzzzzzzzzz"
45
37
392289611
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazazzzzzzzzzzzzzzzzzzzzazzzzzzzzaazaazaazzzzzza"
23
99
37215529
Returns: "aaaaaaaaaaaaaaaaaazzzzzzzzzzazazzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
34
91
683447134
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzazzazzzzzzzzzzzzazzzzzzz"
27
73
116752252
Returns: "aaaaaaaaaaaaaaaaaaaaazzzzzzazzzzzzzzzzzzzazazzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazazzzz"
5
69
69909135
Returns: ""
84
44
21417563
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazazzzazzzzzzzzzzazzazzzzzzazzzzzzazzzzazzzzzzzzzzzz"
96
99
901413353
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzazzazazzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzazz"
96
90
960567224
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazaazzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzazzzzzzzzzzazzzzzzzzzzzzzzzzazzzzzzzzzzzzz"
97
99
935766290
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzaazzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzaazzzzzzzzzzzzzzzzzzzz"
97
95
900597006
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzzzazzzzzzzazzzzzzzzzzzzzzazzzzzzzzzzzazazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzz"
99
97
992289607
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazaazzzzzzaazzzzzzzzzzzzzzzzzzzz"
7
91
413056
Returns: "aaazzzazzzzzzazzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
7
99
567066
Returns: "aaazzzazzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
8
92
766256
Returns: "aaaazzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzazzzzzzazzzz"
17
25
999999999
Returns: "aaaaazazzzzzzzazaazazazazzzzzaazzazzzazzza"
14
1
1000000000
Returns: ""
17
4
999999999
Returns: ""
100
100
1
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
85
77
1000000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzazzzzzzzzzzzzzzzzzzzzazzzzzzzzzzazazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzazzzaz"
99
99
999998758
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzazzzzzzazzzzzzzzzzzazzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzazzzzzzzzzzzzz"
99
99
9765877
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzazzzzzzzazzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzz"
100
100
999996565
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzazzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzazzzazzzzzzzzzzzzzzzzzzzazzzzzzzz"
100
100
10000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzazzzzzzzzzzz"
100
50
1000000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzazzzzzzzzzzazzazzzzzzaazzzzzzzzzzzzzaazzzzzzazzzzzzzzz"
100
100
999999999
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzazzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzazzzzzazzzzzzzzzzzazzzzz"
79
98
12345678
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzaazzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzazzzzzzz"
100
100
9987678
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzazzzzzzazzzzzzzzzzazzzzzzzzzzzzzazzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
100
100
100100100
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzazzz"
97
98
575111539
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzazzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzazzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzazz"
100
100
10000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzazzzzzzazzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzazzzzzz"
100
100
1000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzazzzazzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
99
99
100000001
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazazazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzaazzzzzzzzzzzzzzzzz"
100
100
100000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazaazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzza"
50
50
100000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzazzzzzzazzzazzzzzzzzzzzzazzzzzzzazazazzzzzzzzzzzzzzzzz"
100
100
10000001
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzazzzzzzazzzzzzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzazzzzzzzzzazzzzz"
99
99
999999999
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzazzzzzzazzzzzzzzzzzazzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzazzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
99
99
1000000000
Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaazzzzzzzzzzzzzzzazzzzzzazzzzzzzzzzzazzzzzzzzzazzzzzzzzzzzzzzzzzzzzzzzazzzzazzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"