Advertisement
florence20

Untitled

Apr 16th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.82 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
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement