diff options
| -rw-r--r-- | 01/twofive.cpp | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/01/twofive.cpp b/01/twofive.cpp new file mode 100644 index 0000000..f6a1141 --- /dev/null +++ b/01/twofive.cpp @@ -0,0 +1,73 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair<int, int>; +constexpr int MX = 5; + +char A[MX*MX]; +bitset<MX*MX> vis; +map<vector<int>, int> dp; + +int f(vector<int> & v) { + for (int i = 1; i < MX; ++i) if (v[i-1] < v[i]) return 0; + for (int i = 0; i < MX; ++i) if (v[i] > MX) return 0; + + int sum = 0; + for (int i = 0; i < MX; ++i) sum += v[i]; + if (sum == MX*MX) return 1; + + if (dp.find(v) != dp.end()) return dp[v]; + + int ret = 0; + for (int i = 0; i < MX; ++i) + if (A[i*MX+v[i]] == 'A'+sum || !A[i*MX+v[i]]) + ++v[i], ret += f(v), --v[i]; + return dp[v] = ret; +} + +string getk(int k) { + string ret(MX*MX, '0'); + + vis.reset(); + memset(A, 0, sizeof A); + for (int i = 0; i < MX*MX; ++i) { + for (int j = 0; j < MX*MX; ++j) { + if (vis[j]) continue; + vis[j] = 1; + + A[i] = 'A'+j; + dp.clear(); + vector<int> v(MX, 0); + int tmp = f(v); + + if (tmp >= k) break; + k -= tmp; + vis[j] = 0; + } + ret[i] = A[i]; + } + return ret; +} + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + ios_base::sync_with_stdio(0), cin.tie(0); + + char c; cin >> c; + if (c == 'N') { + int M; cin >> M; + cout << getk(M); + } + else { + string S; cin >> S; + int l = 0, h = 1e9; + while (l < h) { + int m = (l+h)/2; + string tmp = getk(m); + tmp < S ? l = m+1 : h = m; + } + cout << l; + } +} |