fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e3;
  9. const ll INF = 3e18;
  10.  
  11. int n, k, mx = 0, level = 0;
  12. ll dp[maxn + 10][maxn + 10][2], ans = 1, p;
  13. string s;
  14. vector<char> stk, tmp, res;
  15.  
  16. void add(ll &a, ll b)
  17. {
  18. a += b;
  19. a = min(a, INF);
  20. }
  21. bool is_open(char c)
  22. {
  23. return c == '(' || c == '[' || c == '{';
  24. }
  25.  
  26. int main()
  27. {
  28. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  29. if (fopen("BRCNT1.INP", "r"))
  30. {
  31. freopen("BRCNT1.INP", "r", stdin);
  32. freopen("BRCNT1.OUT", "w", stdout);
  33. }
  34.  
  35. cin >> n >> k;
  36. cin >> s;
  37. s = ' ' + s;
  38. cin >> p;
  39.  
  40. dp[n + 1][0][0] = 1;
  41. for (int i = n + 1; i - 1; i--)
  42. for (int j = 0; j <= k; j++)
  43. for (int t = 0; t <= 1; t++)
  44. {
  45. add(dp[i - 1][j + 1][t || (j + 1 == k)], dp[i][j][t]);
  46. if (j)
  47. add(dp[i - 1][j - 1][t], 3 * dp[i][j][t]);
  48. }
  49. for (int i = 1; i <= n; i++)
  50. {
  51. level += is_open(s[i]) ? 1 : -1;
  52. mx = max(mx, level);
  53. if (s[i] == '(')
  54. continue;
  55. if (s[i] == '[')
  56. {
  57. ans += dp[i + 1][level][1];
  58. if (mx == k)
  59. ans += dp[i + 1][level][0];
  60. }
  61. else if (s[i] == '{')
  62. {
  63. ans += 2 * dp[i + 1][level][1];
  64. if (mx == k)
  65. ans += 2 * dp[i + 1][level][0];
  66. }
  67. else if (level + 2 <= k)
  68. {
  69. ans += 3 * dp[i + 1][level + 2][1];
  70. if (mx == k || level + 2 == k)
  71. ans += 3 * dp[i + 1][level + 2][0];
  72. }
  73. }
  74. cout << ans, el;
  75. level = 0;
  76. mx = 0;
  77. for (int i = 1; i <= n; i++)
  78. {
  79. mx = max(mx, level);
  80. if (mx == k)
  81. {
  82. if (level + 1 <= k)
  83. {
  84. ll m = dp[i + 1][level + 1][0] + dp[i + 1][level + 1][1];
  85. if (m >= p)
  86. {
  87. tmp.push_back('(');
  88. level++;
  89. continue;
  90. }
  91. else
  92. p -= m;
  93. if (m >= p)
  94. {
  95. tmp.push_back('[');
  96. level++;
  97. continue;
  98. }
  99. else p -= m;
  100. if (m >= p)
  101. {
  102. tmp.push_back('{');
  103. level++;
  104. continue;
  105. }
  106. else p -= m;
  107. }
  108. tmp.push_back(')');
  109. level--;
  110. }
  111. else
  112. {
  113. if (level + 1 <= k)
  114. {
  115. ll m = dp[i + 1][level + 1][1];
  116. if (m >= p)
  117. {
  118. tmp.push_back('(');
  119. level++;
  120. continue;
  121. }
  122. else
  123. p -= m;
  124. if (m >= p)
  125. {
  126. tmp.push_back('[');
  127. level++;
  128. continue;
  129. }
  130. else p -= m;
  131. if (m >= p)
  132. {
  133. tmp.push_back('{');
  134. level++;
  135. continue;
  136. }
  137. else p -= m;
  138. }
  139. tmp.push_back(')');
  140. level--;
  141. }
  142. }
  143. for (char c : tmp)
  144. {
  145. if (c == ')')
  146. {
  147. if (stk.back() == '(')
  148. res.push_back(')');
  149. if (stk.back() == '[')
  150. res.push_back(']');
  151. if (stk.back() == '{')
  152. res.push_back('}');
  153. stk.pop_back();
  154. }
  155. else
  156. {
  157. stk.push_back(c);
  158. res.push_back(c);
  159. }
  160. }
  161. for (char c : res)
  162. cout << c;
  163. }
  164.  
Success #stdin #stdout 0s 5316KB
stdin
Standard input is empty
stdout
1