Source code for submission s773

fq.cpp

  1. #include <cstdio>
  2.  
  3. #define MOD 1000000
  4.  
  5. using namespace std;
  6.  
  7. char buffer[1024];
  8.  
  9. int pocet(int i, int v, int p, int d)
  10. {
  11. if (v < 0) return 0;
  12. if (p == 0 || d == 0) return 1;
  13.  
  14. if (buffer[i] == '(')
  15. return pocet(i+1, v+1, p-1, d) % MOD;
  16. else if (buffer[i] == ')')
  17. return pocet(i+1, v-1, p, d-1) % MOD;
  18.  
  19. return (pocet(i+1, v+1, p-1, d) % MOD) + (pocet(i+1, v-1, p, d-1) % MOD);
  20. }
  21.  
  22. int main()
  23. {
  24. int n;
  25.  
  26. while (scanf("%s%n%*c", buffer, &n) != EOF)
  27. {
  28. printf("%d\n", pocet(0, 0, n/2, n/2) % MOD);
  29. }
  30.  
  31. return 0;
  32. }
  33.