SialenyNixonovQueue.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package senseofsecuritz;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
 
/**
 *
 * @author istenik3
 */
public class SialenyNixonovQueue {
    static public void main(String [] arguments) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
 
        String line;
        while((line = reader.readLine()) != null) {
            if(line.charAt(0) == ')') {
                System.out.println(0);
                continue;
            }
 
            int [][] matica = new int[1001][1001];
 
            matica[0][0] = 1;
 
            for(int stlpec=1; stlpec<line.length()+1; stlpec++) {
                for(int riadok=0; riadok<=line.length()/2; riadok++) {
                    int index = stlpec-1;
                    char c = line.charAt(index);
 
                    if(c == '.') {
                        int a = (riadok-1 >= 0 ? matica[riadok-1][stlpec-1] : 0);
                        int b = (riadok+1 < 1001 ? matica[riadok+1][stlpec-1] : 0);
 
                        matica[riadok][stlpec] = a + b;
                    } else if(c == '(') {
                        if(riadok-1 >= 0)
                            matica[riadok][stlpec] = matica[riadok-1][stlpec-1];
                    } else if(c == ')') {
                        if(riadok+1 < 1001)
                            matica[riadok][stlpec] = matica[riadok+1][stlpec-1];
                    }
 
                    matica[riadok][stlpec] = matica[riadok][stlpec] % 1000000;
                }
            }
 
            /*for(int i=0; i<10; i++) {
                for(int j=0; j<10; j++) {
                    System.out.print(matica[i][j]);
                   
                }
                System.out.println();
            }*/
 
            System.out.println(matica[0][line.length()]);
        }
    }
}