Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <string>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <assert.h>
  8.  
  9. using namespace std;
  10.  
  11. int main() {
  12.     int n;
  13.     long long int k;
  14.     scanf("%d %lld", &n, &k);
  15.     long long int** dp = new long long int*[2 * n + 1];
  16.     for (int i = 0; i <= 2 * n; i++) {
  17.         dp[i] = new long long int[2 * n];
  18.         for (int j = 0; j <= 2 * n; j++)
  19.             dp[i][j] = 0;
  20.     }
  21.     dp[2 * n][0] = 1;
  22.     for (int i = 2 * n - 1; i >= 0; i--) {
  23.         for (int j = 0; j <= 2 * n; j++) {
  24.             dp[i][j] = 0;
  25.             if (j > 0) dp[i][j] += dp[i + 1][j - 1];
  26.             if (j < 2 * n) dp[i][j] += 2 * dp[i + 1][j + 1];
  27.         }
  28.     }
  29.     long long int w = 0;
  30.     char* stk = new char[2 * n];
  31.     int s = 0;
  32.     int bal = 0;
  33.     k--;
  34.     for (int i = 0; i < 2 * n; i++) {
  35.         long long int cnt = 0;
  36.         if (s > 0 && stk[s - 1] == '(') cnt += dp[i + 1][bal - 1];
  37.         if (s > 0 && stk[s - 1] == '[' && w + 2 * dp[i + 1][bal + 1] <= k) {
  38.             printf("]");
  39.             s--;
  40.             w += 2 * dp[i + 1][bal + 1];
  41.             bal--;
  42.         }
  43.         else if (dp[i + 1][bal + 1] > 0 && w + dp[i + 1][bal + 1] + cnt <= k) {
  44.             printf("[");
  45.             stk[s++] = '[';
  46.             w += dp[i + 1][bal + 1] + cnt;
  47.             bal++;
  48.         }
  49.         else if (s > 0 && stk[s - 1] == '(' && w + dp[i + 1][bal + 1] <= k) {
  50.             printf(")");
  51.             s--;
  52.             w += dp[i + 1][bal + 1];
  53.             bal--;
  54.         }
  55.         else {
  56.             printf("(");
  57.             bal++;
  58.             stk[s++] = '(';
  59.         }
  60.     }
  61.     system("pause");
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement