Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <cstring>
- #include <assert.h>
- using namespace std;
- int main() {
- int n;
- long long int k;
- scanf("%d %lld", &n, &k);
- long long int** dp = new long long int*[2 * n + 1];
- for (int i = 0; i <= 2 * n; i++) {
- dp[i] = new long long int[2 * n];
- for (int j = 0; j <= 2 * n; j++)
- dp[i][j] = 0;
- }
- dp[2 * n][0] = 1;
- for (int i = 2 * n - 1; i >= 0; i--) {
- for (int j = 0; j <= 2 * n; j++) {
- dp[i][j] = 0;
- if (j > 0) dp[i][j] += dp[i + 1][j - 1];
- if (j < 2 * n) dp[i][j] += 2 * dp[i + 1][j + 1];
- }
- }
- long long int w = 0;
- char* stk = new char[2 * n];
- int s = 0;
- int bal = 0;
- k--;
- for (int i = 0; i < 2 * n; i++) {
- long long int cnt = 0;
- if (s > 0 && stk[s - 1] == '(') cnt += dp[i + 1][bal - 1];
- if (s > 0 && stk[s - 1] == '[' && w + 2 * dp[i + 1][bal + 1] <= k) {
- printf("]");
- s--;
- w += 2 * dp[i + 1][bal + 1];
- bal--;
- }
- else if (dp[i + 1][bal + 1] > 0 && w + dp[i + 1][bal + 1] + cnt <= k) {
- printf("[");
- stk[s++] = '[';
- w += dp[i + 1][bal + 1] + cnt;
- bal++;
- }
- else if (s > 0 && stk[s - 1] == '(' && w + dp[i + 1][bal + 1] <= k) {
- printf(")");
- s--;
- w += dp[i + 1][bal + 1];
- bal--;
- }
- else {
- printf("(");
- bal++;
- stk[s++] = '(';
- }
- }
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement