#![allow(unused_imports)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::io::Write; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn infinite_sum(a: f64, r: f64) -> f64 { a / (1. - r) } fn main() { let n = read::(); let a = read_vec::(); let a_prob = a .iter() .map(|&x| { infinite_sum( 1.0 / x as f64, (1.0 - 1.0 / x as f64) * (1.0 - 1.0 / x as f64), ) }) .collect::>(); debug!(a_prob); let asum = a.iter().sum::(); let mut dp = vec![vec![vec![0.0; 2]; 1 << n]; 1 << n]; for state in 0..1 << n { let mut kiri_score = 0; for j in 0..n { if (state >> j) & 1 == 1 { kiri_score += a[j]; } if kiri_score >= asum - kiri_score { for k in 0..2 { dp[(1 << n) - 1][state][k] = 1.0; } } } } for s_state in (0..(1 << n) - 1).rev() { 'p: for p_state in 0..1 << n { for j in 0..n { if (s_state >> j) & 1 == 0 && (p_state >> j) & 1 == 1 { continue 'p; } } let unselected = (0..n) .filter(|&x| (s_state >> x) & 1 == 0) .collect::>(); // cur senkou let mut temp = 0.0; for &ai in &unselected { let next_s_state = s_state | (1 << ai); let next_p_state = p_state | (1 << ai); let prob = a_prob[ai]; temp = f64::max( temp, prob * dp[next_s_state][next_p_state][1] + (1.0 - prob) * dp[next_s_state][p_state][0], ); } dp[s_state][p_state][0] = temp; let mut temp = 1.0; for &ai in &unselected { let next_s_state = s_state | (1 << ai); let next_p_state = p_state | (1 << ai); let prob = a_prob[ai]; temp = f64::min( temp, (1.0 - prob) * dp[next_s_state][next_p_state][1] + prob * dp[next_s_state][p_state][0], ); } dp[s_state][p_state][1] = temp; } } let ans = 1.0 - dp[0][0][1]; println!("{}", ans); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() }