-
Notifications
You must be signed in to change notification settings - Fork 0
/
Netease_XiaoyiDictionary.cpp
75 lines (67 loc) · 1.53 KB
/
Netease_XiaoyiDictionary.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//
// Created by hfq on 2019/8/31.
//
#include <iostream>
#include <string>
class Solution {
public:
Solution(int n, int m) {
numa = n;
numz = m;
}
std::string dictionary(int k) {
std::string res(numa + numz, 'a');
long long comb;
for(int i = 0; i < res.size(); i++) {
if(k == 1) {
for(int j = i + numa; j < i + numa + numz; j++) {
res[j] = 'z';
}
break;
}
comb = combination(res.size()-i-1, numz, k);
if(comb > 0 && k > comb) {
res[i] = 'z';
numz--;
k -= comb;
}
else {
numa--;
}
}
return res;
}
long long combination(int n, int m, int k) {
if(m > n) {
return -1;
}
if(m > n / 2) {
m = n - m;
}
long long res = 1;
for(int i = 0; i < m; i++) {
res *= n-i;
res /= i + 1;
if(res > k) {
return -1;
}
}
return res;
}
int numa;
int numz;
};
int main(int argc, char** argv) {
int n = 0, m = 0, k = 0;
std::cin >> n >> m >> k;
auto sol = Solution(n, m);
long long comb = sol.combination(n + m, n, k);
if(comb != -1 && comb < k) {
std::cout << -1 << std::endl;
}
else {
auto&& res = sol.dictionary(k);
std::cout << res << std::endl;
}
return 0;
}