use fio::*; use std::cmp::Reverse; mod rng { use std::ops::{ Bound::{Excluded, Included, Unbounded}, Range, RangeBounds, }; pub trait SmallInt { fn rng_size_u64>(rng: &T) -> Option; fn pick_nth>(rng: &T, nth: u64) -> Self; } macro_rules! small_int { ($($SelfT:ty)*) => { $(impl SmallInt for $SelfT { fn rng_size_u64>(rng: &T) -> Option { let start_inclusive = match rng.start_bound() { Included(x) => *x, Excluded(x) => if *x != Self::MAX { x+1 } else {return Some(0)}, Unbounded => Self::MIN, }; let end_inclusive = match rng.end_bound() { Included(x) => *x, Excluded(x) => if *x != Self::MIN { x-1 } else { return Some(0); }, Unbounded => Self::MAX, }; if start_inclusive > end_inclusive { Some(0u64) } else { (end_inclusive as u64).wrapping_sub(start_inclusive as u64).checked_add(1) } } fn pick_nth>(rng: &T, nth: u64) -> Self { (match rng.start_bound() { Included(x) => ((*x) as u64) + nth, Excluded(x) => ((*x) as u64).wrapping_add(nth).wrapping_sub(1), Unbounded => (Self::MIN as u64) + nth, }) as Self } })* } } small_int!(i8 i16 i32 i64 u8 u16 u32 u64); #[cfg(any( target_pointer_width = "16", target_pointer_width = "32", target_pointer_width = "64" ))] small_int!(usize isize); pub struct SplitMix64 { x: u64, } impl SplitMix64 { pub fn new(seed: u64) -> Self { Self { x: seed } } pub fn next(&mut self) -> u64 { self.x = self.x.wrapping_add(0x9e3779b97f4a7c15); let mut z = self.x; z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9); z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb); z ^ (z >> 31) } #[cold] fn _cold_sample(&mut self, n: u64, mut m: u128, mut l: u64) -> u64 { let t = n.wrapping_neg() % n; while l < t { m = (self.next() as u128) * (n as u128); l = m as u64; } (m >> 64) as u64 } /// Generate number from range from 0..n, i.e. from 0 to n, including 0 and excluding n. pub fn sample(&mut self, n: u64) -> u64 { assert_ne!(n, 0, "Cannot sample from empty range"); // Lemire let m = (self.next() as u128) * (n as u128); let l = m as u64; if l < n { return self._cold_sample(n, m, l); } (m >> 64) as u64 } /// Uniformly sample from range pub fn sample_range>(&mut self, rng: R) -> T { let nth = match T::rng_size_u64(&rng) { None => self.next(), Some(v) => self.sample(v), }; T::pick_nth(&rng, nth) } /// All values that can be generated are form of n * eps/2, for 0.0..1.0 pub fn next_f64(&mut self) -> f64 { let sig = 1u64 << f64::MANTISSA_DIGITS; let val = self.sample(sig) as f64; val / sig as f64 } /// Uniformly sample from uniform distribution. Only accept standard Range. /// All values that can be generated are form of n * eps/2, for 0.0..1.0 pub fn sample_uniform(&mut self, rng: Range) -> f64 { let p = self.next_f64(); rng.start * p + rng.end * (1.0 - p) } /// Returns true of probability p pub fn next_bool(&mut self, p_true: f64) -> bool { assert!((0.0..=1.0).contains(&p_true)); self.next_f64() < p_true } } } fn main() { let [n, pa, pb] = read_tuple::(); let n: usize = n.parse().unwrap(); let (pa, pb): (f64, f64) = (pa.parse().unwrap(), pb.parse().unwrap()); let mut a = read_vec::(); let mut b = read_vec::(); a.sort_unstable_by_key(|x| Reverse(*x)); b.sort_unstable_by_key(|x| Reverse(*x)); let mut rng = rng::SplitMix64::new(0x1723); let find_idx = |n: usize, p: f64, v: f64| -> usize { if v < p { n - 1 } else { let v = (v - p) / (1.0 - p); (v * (n - 1) as f64) as usize } }; const ROUND: i32 = 10_000_000; let mut ans = 0; let cutoff = a.iter().sum::() + b.iter().sum::(); for _ in 0..ROUND { let mut a = a.clone(); let mut b = b.clone(); let mut a_win = 0; let mut b_win = 0; for i in 0..n { let sa = find_idx(n - i, pa, rng.next_f64()); let sb = find_idx(n - i, pb, rng.next_f64()); if a[sa] > b[sb] { a_win += a[sa] + b[sb]; } else { b_win += a[sa] + b[sb]; } a.remove(sa); b.remove(sb); if a_win >= cutoff / 2 + 1 || b_win >= (cutoff + 1) / 2 { break; } } if a_win > b_win { ans += 1 } } println!("{:.7}", ans as f64 / ROUND as f64); } mod fio { use std::{ cell::RefCell, convert::TryInto, fmt::Debug, io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout}, str::FromStr, }; thread_local! { pub static STDIN: RefCell> = RefCell::new(stdin().lock()); pub static STDOUT: RefCell>> = RefCell::new(BufWriter::new(stdout().lock())); } #[allow(dead_code)] pub fn read() -> T where ::Err: Debug, { read_line().parse().unwrap() } #[allow(dead_code)] pub fn read_vec() -> Vec where ::Err: Debug, { read_line() .split_whitespace() .map(|x| x.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn read_tuple() -> [T; N] where T: FromStr + Debug, ::Err: Debug, { read_vec::().try_into().unwrap() } /// whitespace at the end of the line is ignored pub fn read_line() -> String { let mut s = String::new(); STDIN.with(|cell| { cell.borrow_mut().read_line(&mut s).unwrap(); }); String::from_str(s.trim_end()).unwrap() } } #[macro_export] macro_rules! print { ($($t:tt)*) => { fio::STDOUT.with(|cell|{ use std::io::Write; write!(cell.borrow_mut(), $($t)*).unwrap() })}; } #[macro_export] macro_rules! println { ($($t:tt)*) => { fio::STDOUT.with(|cell| { use std::io::Write; writeln!(cell.borrow_mut(), $($t)*).unwrap() }) }; } #[macro_export] macro_rules! flush { () => { fio::STDOUT.with(|cell| { use std::io::Write; cell.borrow_mut().flush().unwrap() }); }; }