Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.85 KB | None | 0 0
  1. import java.math.*;
  2. import java.text.*;
  3.  
  4. class Main {
  5.   static double result;
  6.   static double[] prob;
  7.   static double[] flies;
  8.   static int leaves;
  9.  
  10.    //static double[][] DP; // temp results
  11.  
  12.     public static void main(String[] args) {
  13.         // Uncomment this line if you want to read from a file
  14.         In.open("public/sample.in");
  15.        
  16.         int t = In.readInt();
  17.         for (int i = 0; i < t; i++) {
  18.             testCase();
  19.         }
  20.        
  21.         // Uncomment this line if you want to read from a file
  22.         //In.close();
  23.     }
  24.  
  25.     public static void testCase() {
  26.         // Input using In.java class
  27.         int leaves = In.readInt();
  28.         //Out.print(leaves + " ");
  29.         int startleaf = In.readInt();
  30.         //Out.print(startleaf+ " ");
  31.         int jumps = In.readInt();
  32.         //Out.println(jumps);
  33.        
  34.         flies = new double[leaves+1];
  35.         prob = new double[leaves+1];
  36.         //save values of probs for each leaf :
  37.         for(int i = 0; i<leaves; i++){
  38.           flies[i] = In.readInt();
  39.           //Out.print(flies[i] + " ");
  40.         }
  41.        // Out.println();
  42.         for(int i = 0; i<leaves; i++){
  43.           prob[i] = In.readDouble();
  44.           //Out.print(prob[i] + " ");
  45.         }
  46.         //Out.println();
  47.        
  48.         //DP = new double[leaves+1][jumps+1];
  49.       //initial number of flies eaten
  50.       /*for(int i = 0; i<=leaves; i++){
  51.         for(int j = 0; j<=jumps; j++){
  52.           DP[i][j] = -1.0;// DP[i][j] : number of flies eaten, with j jumps, starting at leaf i
  53.         }
  54.       }*/
  55.        
  56.         DecimalFormat df = new DecimalFormat("0.0####");
  57.         df.setRoundingMode(RoundingMode.HALF_DOWN);
  58.         System.out.println(df.format(calcul(startleaf, jumps)));
  59.     }
  60.    
  61.     static double calcul(int startleaf, int jumps){
  62.       /*if (DP[startleaf][jumps] != -1.0) {//we already have the result
  63.         return DP[startleaf][jumps];
  64.       }*/
  65.       if (jumps == 0){
  66.         if(startleaf>=0 && startleaf<=leaves){
  67.         return flies[startleaf];
  68.         }
  69.       }
  70.       /*if(startleaf<0 || startleaf>leaves){
  71.       }
  72.      
  73.       double sum = 0.0;
  74.       double left = 0.0;
  75.       double right = 0.0;
  76.       for(int i = 0; i<jumps; i++){//nombre d'additions
  77.         if(startleaf==0){
  78.           if(1-prob[startleaf] == 1.0){//si la prob d'aller à droite ==1
  79.             sum *= (1-prob[startleaf])*calcul(startleaf+1, jumps-1);
  80.             return flies[startleaf] + sum;
  81.           }
  82.           else{
  83.             if(prob[startleaf] == 1.0){
  84.             return flies[startleaf];
  85.           }
  86.           }
  87.         }
  88.         else if(startleaf==leaves){
  89.           if(prob[startleaf] == 1.0){
  90.           sum *= prob[startleaf]*calcul(startleaf-1, jumps-1);
  91.           return flies[startleaf] + sum;
  92.           }
  93.           else if(prob[startleaf] == 0.0){
  94.             return flies[startleaf];
  95.           }
  96.         }
  97.         else{
  98.         left *= prob[startleaf]*calcul(startleaf-1, jumps-1);
  99.         right *= (1-prob[startleaf])*calcul(startleaf+1, jumps-1);
  100.         return flies[startleaf] + left + right;
  101.         //sum += prob[startleaf]*flies[startleaf-1] + (1-prob[startleaf])*flies[startleaf+1];
  102.         }
  103.       }
  104.       return sum;*/
  105.      
  106.       if(startleaf == leaves){
  107.          DP[startleaf][jumps] = prob[startleaf]*flies[startleaf-1];
  108.          return flies[startleaf] + DP[startleaf][jumps];
  109.       }
  110.       else if(startleaf == 0){
  111.         DP[startleaf][jumps] = flies[startleaf] + (1-prob[startleaf])*flies[startleaf+1];
  112.       }
  113.       else{
  114.       DP[startleaf][jumps] = flies[startleaf] + prob[startleaf]*calcul(startleaf-1, jumps-1) + (1-prob[jumps])*calcul(startleaf, jumps-1);
  115.      
  116.       //DP[startleaf][jumps] = prob[startleaf]*flies[startleaf-1] + (1-prob[startleaf])*flies[startleaf+1];
  117.       }
  118.       return DP[startleaf][jumps];
  119.     }
  120.  
  121.  
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement