Source code for submission s1034

fq.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8. #include <queue>
  9.  
  10. using namespace std;
  11.  
  12. int catalan(int n){
  13. int c=1;
  14. for (int i=1; i<=n;i++)
  15. c=4*c-6*c/(i+1);
  16. return c;
  17. }
  18.  
  19. vector< vector<bool> > ok;//kam muze zavorka
  20.  
  21. int main()
  22. {
  23. vector<vector<int> > v;
  24. string s;
  25. while(cin>>s){
  26. //ok.clear();
  27. //ok.resize(s.size());
  28. v.clear();
  29. v.resize(s.size());
  30. for(int i=0;i<s.size();i++){
  31. // ok[i].resize(s.size());
  32. v[i].resize(s.size());
  33. for(int j=0;j<s.size();j++)
  34. {
  35. v[i][j]=0;
  36. //ok[i][j]=true;
  37. //ok[j][i]=true;
  38. //if(s[j]=='.'){
  39. //ok[i][j]=true;
  40. //}
  41. //else
  42. // if(s[j]=='('){
  43. // ok[i][j]==false;
  44. // }
  45. // else{
  46. // ok[j][i]=false;
  47. // }
  48. }
  49. }//end init for
  50.  
  51. //dynamika
  52. v[0][0]=1;
  53. for(int i=0;i<=s.size()/2;i++){
  54. for(int j=0;j<=i;j++){
  55.  
  56. /*if(j>0&&ok[i][j-1])
  57. v[i][j]+=v[i][j-1];
  58. if(i>0&&ok[i-1][j])
  59. v[i][j]+=v[i-1][j];*/
  60.  
  61. if(j>0&&s[i+j-1]!='(')
  62. v[i][j]+=v[i][j-1];
  63. if(i!=j&&s[i+j-1]!=')')
  64. v[i][j]+=v[i-1][j];
  65. v[i][j]%=1000000;
  66. }
  67. }
  68. cout<<v[s.size()/2][s.size()/2]<<endl;
  69. //cout<<catalan(s.size()/2)<<endl;
  70. }
  71. return 0;
  72. }
  73.