Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.*;
- import java.text.*;
- class Main {
- static double result;
- static double[] prob;
- static double[] flies;
- static int leaves;
- //static double[][] DP; // temp results
- public static void main(String[] args) {
- // Uncomment this line if you want to read from a file
- In.open("public/sample.in");
- int t = In.readInt();
- for (int i = 0; i < t; i++) {
- testCase();
- }
- // Uncomment this line if you want to read from a file
- //In.close();
- }
- public static void testCase() {
- // Input using In.java class
- int leaves = In.readInt();
- //Out.print(leaves + " ");
- int startleaf = In.readInt();
- //Out.print(startleaf+ " ");
- int jumps = In.readInt();
- //Out.println(jumps);
- flies = new double[leaves+1];
- prob = new double[leaves+1];
- //save values of probs for each leaf :
- for(int i = 0; i<leaves; i++){
- flies[i] = In.readInt();
- //Out.print(flies[i] + " ");
- }
- // Out.println();
- for(int i = 0; i<leaves; i++){
- prob[i] = In.readDouble();
- //Out.print(prob[i] + " ");
- }
- //Out.println();
- //DP = new double[leaves+1][jumps+1];
- //initial number of flies eaten
- /*for(int i = 0; i<=leaves; i++){
- for(int j = 0; j<=jumps; j++){
- DP[i][j] = -1.0;// DP[i][j] : number of flies eaten, with j jumps, starting at leaf i
- }
- }*/
- DecimalFormat df = new DecimalFormat("0.0####");
- df.setRoundingMode(RoundingMode.HALF_DOWN);
- System.out.println(df.format(calcul(startleaf, jumps)));
- }
- static double calcul(int startleaf, int jumps){
- /*if (DP[startleaf][jumps] != -1.0) {//we already have the result
- return DP[startleaf][jumps];
- }*/
- if (jumps == 0){
- if(startleaf>=0 && startleaf<=leaves){
- return flies[startleaf];
- }
- }
- /*if(startleaf<0 || startleaf>leaves){
- }
- double sum = 0.0;
- double left = 0.0;
- double right = 0.0;
- for(int i = 0; i<jumps; i++){//nombre d'additions
- if(startleaf==0){
- if(1-prob[startleaf] == 1.0){//si la prob d'aller à droite ==1
- sum *= (1-prob[startleaf])*calcul(startleaf+1, jumps-1);
- return flies[startleaf] + sum;
- }
- else{
- if(prob[startleaf] == 1.0){
- return flies[startleaf];
- }
- }
- }
- else if(startleaf==leaves){
- if(prob[startleaf] == 1.0){
- sum *= prob[startleaf]*calcul(startleaf-1, jumps-1);
- return flies[startleaf] + sum;
- }
- else if(prob[startleaf] == 0.0){
- return flies[startleaf];
- }
- }
- else{
- left *= prob[startleaf]*calcul(startleaf-1, jumps-1);
- right *= (1-prob[startleaf])*calcul(startleaf+1, jumps-1);
- return flies[startleaf] + left + right;
- //sum += prob[startleaf]*flies[startleaf-1] + (1-prob[startleaf])*flies[startleaf+1];
- }
- }
- return sum;*/
- if(startleaf == leaves){
- DP[startleaf][jumps] = prob[startleaf]*flies[startleaf-1];
- return flies[startleaf] + DP[startleaf][jumps];
- }
- else if(startleaf == 0){
- DP[startleaf][jumps] = flies[startleaf] + (1-prob[startleaf])*flies[startleaf+1];
- }
- else{
- DP[startleaf][jumps] = flies[startleaf] + prob[startleaf]*calcul(startleaf-1, jumps-1) + (1-prob[jumps])*calcul(startleaf, jumps-1);
- //DP[startleaf][jumps] = prob[startleaf]*flies[startleaf-1] + (1-prob[startleaf])*flies[startleaf+1];
- }
- return DP[startleaf][jumps];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement