括号序列

brackets.c/cpp/pas

（2s/256M）

 

【题目描述】

课堂上，Felix刚刚学习了关于括号序列的知识。括号序列是一个只由左括号“(”和右括号“)”构成的序列；进一步的，一个合法的括号序列是指左括号和右括号能够一一匹配的序列。

如果用规范的语言说明，一个合法的括号序列可以有以下三种形式：

1 S=“”（空串），S是一个合法的括号序列；

2 S=XY，其中X，Y均为合法的括号序列，则S也是一个合法的括号序列；

3 S=(X)，其中X为合法的括号序列，则S也是一个合法的括号序列。

 

这时老师在黑板上写出了一个了括号序列：“()))()”。

Felix一眼就看出这个序列并不是合法的括号序列。

这时老师提出了一个这样的问题：能否在序列中找出连续的一段，把这一段里面的左括号变成右括号，右括号变成左括号，变换之后整个序列可以变成合法的呢？

Felix想到，可以把[3..5]进行调换，这样序列就会变为()(())，是一个合法的序列。很明显，不止有一种方法可以使整个序列变合法。

这时，老师又在黑板上写出了一个长度为N的括号序列。Felix想，能否对这个序列进行至多一次变换，使它变合法呢？

 

【输入格式】brackets.in

第一行一个整数T，代表数据的组数；接下来T行，每一行一组数据。

每组数据一行，代表给出的括号序列。

【输出格式】brackets.out

输出共T行，对于每组数据，输出“possible”（可以变换）或“impossible”（不可变换）。（不含引号）

【样例输入】

3

()))

)))(

()

【样例输出】

possible

impossible

possible

【数据范围与约束】

对于50%的数据，T<=5, N<=20;

对于100%的数据，T<=10, N<=5000.

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N = 5005;int n;int a[N];int f[2][N][3];string s;void first(){    cin>>s;     n=s.size();    for(int i=0;i
          
           0) f[!pre][j-1][0]=1; else if(a[i]>0) f[!pre][j+1][0]=1; if(a[i]>0&&j>0) f[!pre][j-1][1]=1; else if(a[i]<0) f[!pre][j+1][1]=1; } if(f[pre][j][1]) { if(a[i]>0&&j>0) f[!pre][j-1][1]=1; else if(a[i]<0) f[!pre][j+1][1]=1; if(a[i]<0&&j>0) f[!pre][j-1][2]=1; else if(a[i]>0) f[!pre][j+1][2]=1; } if(f[pre][j][2]) { if(a[i]<0&&j>0) f[!pre][j-1][2]=1; else if(a[i]>0) f[!pre][j+1][2]=1; } } pre=!pre; } int ok= f[pre][0][0] | f[pre][0][1] | f[pre][0][2]; if(ok) printf("possible\n"); else printf("impossible\n"); return ;}int main(){ freopen("brackets.in","r",stdin); freopen("brackets.ans","w",stdout); int t; scanf("%d",&t); while(t--) { first(); work(); } return 0;}