首页 > 专题系列 > Java解POJ > POJ 3744 Scout YYF I [解题报告] Java
2013
11-13

POJ 3744 Scout YYF I [解题报告] Java

Scout YYF I

问题描述 :

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy’s base. After overcoming a series difficulties, YYF is now at the start of enemy’s famous “mine road”. This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1-p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the “mine road” safely.

输入:

The input contains many test cases ended with EOF.
Each test case contains two lines.
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].

输出:

For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.

样例输入:

1 0.5
2
2 0.5
2 4

样例输出:

0.5000000
0.2500000

解题代码:

//* @author: 
import java.util.*;
public class Main{
 
public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    
   double p,p1,p2,p3;
   while (sc.hasNext()) {
       int n=sc.nextInt();
       int a[]=new int[n+1];
       p=sc.nextDouble();
	for (int i=1;i<=n;i++)
           a[i]=sc.nextInt();
	if (a[1]==1) {System.out.println("0.0000000");continue;}
       int now=1;
	p1=0;p2=1;
	for (int i=2;;i++) {
	  p3=p2*p+(1-p)*p1;
	  if (i==a[now]) {
		now++;
		if (now>n) break;
		p3=0;
	  }
	  if (Math.abs(p2-p3)< 1e-8&&Math.abs(p2-p1)<1e-8) i=a[now]-1;
	  p1=p2;p2=p3;
	}
    System.out.printf("%.7f\n",p2*(1-p));
   }
  }
}