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 static final String INPUT_FILE = "ursi.in";
- public static final String OUTPUT_FILE = "ursi.out";
- public static final 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) {
- continue;
- } 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