Source code for submission s721

Go to diff to previous submission

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
 
/**
 *
 * @author cteam94
 */
public class FQ {
    int n;
    String line;
    Integer[][] a;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
 
        while((new FQ()).readLine(br));
    }
 
    public boolean readLine(BufferedReader br) throws IOException {
        line = br.readLine();
        if (line == null) return false;
 
        n = line.length();
        a = new Integer[n/2 + 1][n/2 + 1];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j <=i; j++) {
                a[i][j] = -1;
            }
 
        }
 
        int x = p(0, 0);
        System.out.println(x % 1000000);
 
        return true;
    }
 
    public int p(int o, int c){
        if (o<c || o>n/2) return 0;
        if (o+c==n) return 1;
        if (a[o][c]==-1){
            if (line.charAt(o+c)=='(') a[o][c] = p(o+1,c);
            if (line.charAt(o+c)==')') a[o][c] = p(o,c+1);
            if (line.charAt(o+c)=='.') a[o][c] = p(o+1,c) + p(o,c+1);
        }
 
         return a[o][c];
    }
}
 

Diff to submission s672

--- c5.s672.cteam094.fq.java.0.FQ.java
+++ c5.s721.cteam094.fq.java.0.FQ.java
@@ -16,8 +16,10 @@
     int n;
     String line;
+    Integer[][] a;
     
     public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
+        
         while((new FQ()).readLine(br));
     }
@@ -28,4 +30,11 @@
         
         n = line.length();
+        a = new Integer[n/2 + 1][n/2 + 1];
+        for (int i = 0; i < a.length; i++) {
+            for (int j = 0; j <=i; j++) {
+                a[i][j] = -1;
+            }
+            
+        }
         
         int x = p(0, 0);
@@ -38,8 +47,11 @@
         if (o<c || o>n/2) return 0;
         if (o+c==n) return 1;
-        if (line.charAt(o+c)=='(') return p(o+1,c);
-        if (line.charAt(o+c)==')') return p(o,c+1);
-        if (line.charAt(o+c)=='.') return p(o+1,c) + p(o,c+1);
-        return 0;
+        if (a[o][c]==-1){
+            if (line.charAt(o+c)=='(') a[o][c] = p(o+1,c);
+            if (line.charAt(o+c)==')') a[o][c] = p(o,c+1);
+            if (line.charAt(o+c)=='.') a[o][c] = p(o+1,c) + p(o,c+1);
+        }
+        
+         return a[o][c];
     }
 }