daily pastebin goal
34%
SHARE
TWEET

Untitled

florence20 Apr 16th, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.FileNotFoundException;
  4. import java.io.FileReader;
  5. import java.io.FileWriter;
  6. import java.io.IOException;
  7.  
  8. public class Ursi {
  9.     /*
  10.     * char array de 2000 de caractere, maximul posibil
  11.     * in care voi pune toate toate caracterele citite
  12.     */
  13.     public char[] charachets = new char[2000];
  14.     public final static String INPUT_FILE = "ursi.in";
  15.     public final static String OUTPUT_FILE = "ursi.out";
  16.     public final static long val = (long)(Math.pow(10, 9) + 7);
  17.     long dp[][];
  18.     int lungime = 0;
  19.    
  20.     /*
  21.     * se citeste intr-un string intreg sirul, apoi se face char array
  22.     * pentru a putea analiza ulterior fiecare caracter individual
  23.     */
  24.     public void readInput() throws FileNotFoundException, IOException{
  25.         BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
  26.         int c = 0;
  27.         String first = reader.readLine();
  28.         charachets = first.toCharArray();
  29.         lungime = first.toCharArray().length;
  30.        
  31.   }
  32.    
  33.     public void writeOutput(long res){    
  34.         try {
  35.         BufferedWriter writer = writer = new BufferedWriter(new FileWriter(OUTPUT_FILE));
  36.         writer.write((res % val) + "");
  37.         writer.close();
  38.         } catch (IOException ex) {
  39.             throw new RuntimeException(ex);
  40.         }
  41.   }
  42.     /*
  43.     * completez matricea unde fiecare coloana este un caracter
  44.     * din sirul primit, iar fiecare linie reprezinta numarul
  45.     * posibil de caractere ^, unde maximul este lungime(sir);
  46.     * trebuie tratate corne case-urile cand se ajunge la
  47.     * limita peretelui matriceal; elementul dp[1][0] se cunoaste
  48.     * ca fiind 1, pentru ca fiecare sir incepe cu '^'
  49.     */
  50.     public long afisare(){
  51.         long aux = 0;
  52.         dp = new long[lungime][lungime];
  53.         dp[1][0] = 1;
  54.         for(int j = 1; j < lungime; j++){
  55.             for(int i = 0; i < lungime; i++){
  56.                 if(charachets[j] == '^'){
  57.                     if(i == 0) {
  58.                         aux = dp[i+1][j-1];
  59.                         dp[i][j] = aux % val;
  60.                     } else
  61.                     if(i + 1 == lungime){
  62.                     } else {
  63.                     aux = (dp[i-1][j-1] + (i+1) * dp[i+1][j-1]);
  64.                     dp[i][j] = aux % val;
  65.                     }
  66.                 } else
  67.                     if(charachets[j] == '_'){
  68.                         aux = i * dp[i][j-1];
  69.                         dp[i][j] = aux % val;
  70.                 }
  71.             }
  72.         }
  73.         return dp[0][lungime - 1];
  74.     }    
  75.    
  76.     public void solve() throws IOException{
  77.         readInput();
  78.         writeOutput(afisare());
  79.   }
  80.     public static void main(String[] args) throws IOException {
  81.         new Ursi().solve();
  82.     }
  83.    
  84.    
  85. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top