fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //x = no of '[' - no of ']'
  5. //1)pehle se kaheen kaheen pe "[" daale hue hai jo hamein expressions mile hai usmei 
  6.  
  7. int squarebrackets(char * arr,int n,int x){ // 'x' gives the diffrence between open brackts and closed ones-->
  8.     if(n == 0 && x == 0){ //n == 0 means array khatam ho chuka hai-->x == 0 hona chaiyye kyuki no of open brackets and closed one should be equal
  9.       return 1;
  10.     }
  11.     if(n  == 0 && x != 0){//matlab array khatam but we have more '[' than ']' matlab galat expression--> wont count it 
  12.         return 0;
  13.     }
  14.  
  15.     if(arr[0] == 'z'){ //yahaan kuch nhi hai -->we can put up an open or close
  16.         if(x == 0 ){// special case 1)x == 0 matlab sab baanced hai --> open bracket hi dal sakta hai hence--> x increases  by one
  17.           return squarebrackets(arr + 1,n - 1, 1);
  18.         }
  19.         if(x == n){// special case 2) x == n -> '[' are graeter by just that amount jitna array bacha hai-->ab bache mai sirf '] ' lagega no option
  20.           return 1;
  21.         }else{
  22.             return squarebrackets(arr + 1,n - 1,x + 1) + squarebrackets(arr + 1,n - 1,x - 1); //general case mei ek baar arr[0] ='[' daal ke  ans mangwa lo
  23.                                                                                               //and ek baar ']' baar arr[0]= ']'karke ans mangwa lo then erturn their sum
  24.         }
  25.     }
  26.  
  27.     else if(arr[0] != 'z'){   //it means arr[0] pe '[' already dala hua hai-->so,no option
  28.         //(arr[0] == '['){
  29.             return squarebrackets(arr + 1,n - 1,x + 1);
  30.  
  31.  
  32.     }
  33. }
  34.  
  35. int main()
  36. {
  37.     int A;
  38.     cin >> A;
  39.     for(int c = 0;c < A;c++){
  40.     int n;
  41.     cin >> n;
  42.         n = 2*n;
  43.     char* arr = new char[ n];
  44.     int k;
  45.     for(int i = 0;i <  n;i++){   //i'll fill the array with 'z'
  46.         arr[i] = 'z';
  47.     }
  48.     cin>>k; 
  49.     for(int i = 0;i < k;i++){
  50.         int t;
  51.         cin >> t;
  52.         arr[t-1] = '[';         //jahaan '['daalna hai vaha replace 'z' with '['
  53.     }
  54.  
  55.     int ans = squarebrackets(arr,n,0);//x = 0 bheja hai kyuki abhi that difference is 0
  56.     cout <<  ans << endl;
  57.  
  58. }
  59.     return 0;
  60. }
Time limit exceeded #stdin #stdout 5s 16136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i5l7Q1
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!