expectedcars.java

import java.util.*;
public class expectedcars {
	public static void main(String[] args){
		int n = 100000;
		int l = 10000;
		long z = 0;
		for(int i=0;i<l;i++){
			z+=n-simulate(n);
		}
		System.out.println(((double) z)/((double) l));
	}
	
	public static int simulate(int n){
		ArrayList<Integer> a = new ArrayList<Integer>();
		for(int i=0;i<n;i++){
			a.add(i);
		}
		Collections.shuffle(a);
		
		boolean[] b = new boolean[n];
		for(int i=0;i<n;i++){
			b[i]=true;
		}
		for(int i=0;i<n;i++){
			int t = a.get(i);
			b[t]=false;
			if(t-1>-1&&!b[t-1]){
				return i;
			}
			if(t+1<n&&!b[t+1]){
				return i;
			}
		}
		return n;
	}
}