Advertisement
florence20

Untitled

Apr 16th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None | 0 0
  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 in care voi pune toate toate
  11. * caracterele citite
  12. */
  13. public char[] charachets = new char[2000];
  14. public static final String INPUT_FILE = "ursi.in";
  15. public static final String OUTPUT_FILE = "ursi.out";
  16. public static final 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 pentru a
  22. * 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. /*
  44. * completez matricea unde fiecare coloana este un caracter din sirul primit,
  45. * iar fiecare linie reprezinta numarul posibil de caractere ^, unde maximul
  46. * este lungime(sir); trebuie tratate corne case-urile cand se ajunge la limita
  47. * peretelui matriceal; elementul dp[1][0] se cunoaste ca fiind 1, pentru ca
  48. * 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. continue;
  63. } else {
  64. aux = (dp[i - 1][j - 1] + (i + 1) * dp[i + 1][j - 1]);
  65. dp[i][j] = aux % val;
  66. }
  67. } else 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.  
  81. public static void main(String[] args) throws IOException {
  82. new Ursi().solve();
  83. }
  84.  
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement