Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.FileNotFoundException;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- public class Ursi {
- /*
- * char array de 2000 de caractere, maximul posibil
- * in care voi pune toate toate caracterele citite
- */
- public char[] charachets = new char[2000];
- public final static String INPUT_FILE = "ursi.in";
- public final static String OUTPUT_FILE = "ursi.out";
- public final static long val = (long)(Math.pow(10, 9) + 7);
- long dp[][];
- int lungime = 0;
- /*
- * se citeste intr-un string intreg sirul, apoi se face char array
- * pentru a putea analiza ulterior fiecare caracter individual
- */
- public void readInput() throws FileNotFoundException, IOException{
- BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
- int c = 0;
- String first = reader.readLine();
- charachets = first.toCharArray();
- lungime = first.toCharArray().length;
- }
- public void writeOutput(long res){
- try {
- BufferedWriter writer = writer = new BufferedWriter(new FileWriter(OUTPUT_FILE));
- writer.write((res % val) + "");
- writer.close();
- } catch (IOException ex) {
- throw new RuntimeException(ex);
- }
- }
- /*
- * completez matricea unde fiecare coloana este un caracter
- * din sirul primit, iar fiecare linie reprezinta numarul
- * posibil de caractere ^, unde maximul este lungime(sir);
- * trebuie tratate corne case-urile cand se ajunge la
- * limita peretelui matriceal; elementul dp[1][0] se cunoaste
- * ca fiind 1, pentru ca fiecare sir incepe cu '^'
- */
- public long afisare(){
- long aux = 0;
- dp = new long[lungime][lungime];
- dp[1][0] = 1;
- for(int j = 1; j < lungime; j++){
- for(int i = 0; i < lungime; i++){
- if(charachets[j] == '^'){
- if(i == 0) {
- aux = dp[i+1][j-1];
- dp[i][j] = aux % val;
- } else
- if(i + 1 == lungime){
- } else {
- aux = (dp[i-1][j-1] + (i+1) * dp[i+1][j-1]);
- dp[i][j] = aux % val;
- }
- } else
- if(charachets[j] == '_'){
- aux = i * dp[i][j-1];
- dp[i][j] = aux % val;
- }
- }
- }
- return dp[0][lungime - 1];
- }
- public void solve() throws IOException{
- readInput();
- writeOutput(afisare());
- }
- public static void main(String[] args) throws IOException {
- new Ursi().solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement