Source code for submission s504

fq.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17.  
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25. const int INF = 1<<29;
  26.  
  27. typedef long long ll;
  28.  
  29.  
  30. #define M 1000000
  31.  
  32. char s[1005];
  33. int n;
  34. int f[1005][1005];
  35.  
  36. int main() {
  37. while(scanf("%s",s) == 1){
  38. n = strlen(s);
  39. f[0][0]=1;
  40. FOR(i,1,n){
  41. REP(j,(i+1)){
  42. f[i][j]=0;
  43. if(2*j<i) continue;
  44. if((s[i-1]=='.' || s[i-1]=='(') && j>0) f[i][j]=f[i-1][j-1];
  45. if((s[i-1]=='.' || s[i-1]==')') && j<n) f[i][j]=(f[i][j]+f[i-1][j])%M;
  46. //DEBUG(i); DEBUG(j); DEBUG(f[i][j]);
  47. }
  48. }
  49. printf("%d\n",f[n][n/2]);
  50.  
  51. }
  52. return 0;
  53. }
  54.