Source code for submission s909

Go to diff to previous submission

fq.cpp

  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. char buffer[1024];
  7.  
  8. /*int pocet[512][512][512];
  9.  
  10. int pocet(int i, int v, int p, int d)
  11. {
  12. if (v < 0) return 0;
  13. if (p == 0 || d == 0) return 1;
  14. if (mem[v][p][d] > -1){
  15. return mem[v][p][d];
  16. }
  17. if (buffer[i] == '(')
  18. // mem[v+1][p-1][d] = pocet(i+1, v+1, p-1, d);
  19. return pocet(i+1, v+1, p-1, d);
  20. else if (buffer[i] == ')')
  21. return pocet(i+1, v-1, p, d-1);
  22.  
  23. mem[v][p][d] = pocet(i+1, v+1, p-1, d) + pocet(i+1, v-1, p, d-1);
  24. return mem[v][p][d];
  25. }
  26. */
  27.  
  28. #define MOD 1000000
  29.  
  30. int pocet[1024][1024];
  31.  
  32. static inline void init(int n){
  33. for (int i = 0; i < n; i++){
  34. memset(pocet[i], 0x0, n*sizeof(int));
  35. }
  36. }
  37.  
  38. int main()
  39. {
  40. int n;
  41.  
  42. while (scanf("%s%n%*c", buffer, &n) != EOF)
  43. {
  44.  
  45. if (buffer[0] == ')'){
  46. printf("0\n");
  47. continue;
  48. }
  49.  
  50.  
  51. init(n+1);
  52.  
  53. pocet[1][1] = 1;
  54.  
  55. for (int i = 1; i <= n; i++){
  56. for (int j = 0; j <= i; j++){
  57. if (buffer[i-1] != ')'){
  58. pocet[i][j] += pocet[i-1][j-1] % MOD;
  59. }
  60. if (buffer[i-1] != '('){
  61. pocet[i][j] += pocet[i-1][j+1] % MOD;
  62. }
  63. }
  64. }
  65.  
  66.  
  67. printf("%d\n", pocet[n][0] % MOD);
  68. }
  69.  
  70. return 0;
  71. }
  72.  

Diff to submission s773

fq.cpp

--- c5.s773.cteam024.fq.cpp.0.fq.cpp
+++ c5.s909.cteam024.fq.cpp.0.fq.cpp
@@ -1,5 +1,4 @@
 #include <cstdio>
-
-#define MOD 1000000
+#include <cstring>
 
 using namespace std;
@@ -7,15 +6,32 @@
 char buffer[1024];
 
+/*int pocet[512][512][512];
+
 int pocet(int i, int v, int p, int d)
 {
         if (v < 0) return 0;
         if (p == 0 || d == 0) return 1;
-
+        if (mem[v][p][d] > -1){
+                return mem[v][p][d];
+        }
         if (buffer[i] == '(')
-                return pocet(i+1, v+1, p-1, d) % MOD;
+//              mem[v+1][p-1][d] = pocet(i+1, v+1, p-1, d);
+                return pocet(i+1, v+1, p-1, d);
         else if (buffer[i] == ')')
-                return pocet(i+1, v-1, p, d-1) % MOD;
+                return pocet(i+1, v-1, p, d-1);
 
-        return (pocet(i+1, v+1, p-1, d) % MOD) + (pocet(i+1, v-1, p, d-1) % MOD);
+        mem[v][p][d] = pocet(i+1, v+1, p-1, d) + pocet(i+1, v-1, p, d-1);
+        return mem[v][p][d];
+}
+*/
+
+#define MOD 1000000
+
+int pocet[1024][1024];
+
+static inline void init(int n){
+        for (int i = 0; i < n; i++){
+                        memset(pocet[i], 0x0, n*sizeof(int));
+        }
 }
 
@@ -26,5 +42,28 @@
         while (scanf("%s%n%*c", buffer, &n) != EOF)
         {
-                printf("%d\n", pocet(0, 0, n/2, n/2) % MOD);
+                
+                if (buffer[0] == ')'){
+                        printf("0\n");
+                        continue;
+                }
+
+
+                init(n+1);
+                
+                pocet[1][1] = 1;
+                
+                for (int i = 1; i <= n; i++){
+                        for (int j = 0; j <= i; j++){
+                                if (buffer[i-1] != ')'){
+                                        pocet[i][j] += pocet[i-1][j-1] % MOD;
+                                }
+                                if (buffer[i-1] != '('){
+                                        pocet[i][j] += pocet[i-1][j+1] % MOD;
+                                }
+                        }
+                }
+        
+
+                printf("%d\n", pocet[n][0] % MOD);
         }