TheDictionary | Topcoder Archive

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"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.