use std::borrow::Borrow;

fn product_with_mask<I, F>(arr: I, mask: u64) -> f64
where
    I: IntoIterator<Item = F>,
    F: Borrow<f64>,
{
    #[inline]
    fn adjust(f: f64, bit: u64) -> f64 {
        if bit == 0 {
            1.0 - f
        } else {
            f
        }
    }

    arr.into_iter()
        .enumerate()
        .map(|(i, x)| adjust(*x.borrow(), mask & (1 << i)))
        .product()
}

const SIZE_LIMIT: usize = 63;

fn count_lucky_hunt<I, F>(probs: I, necessary: usize) -> f64
where
    I: IntoIterator<Item = F>,
    F: Borrow<f64>,
    <I as IntoIterator>::IntoIter: ExactSizeIterator + Clone,
{
    use std::iter::ExactSizeIterator;

    let probs = probs.into_iter();
    let len = probs.len();

    if len > SIZE_LIMIT {
        panic!("cannot count result for len > {}", SIZE_LIMIT);
    }

    if necessary > len {
        return 0.0;
    }

    let mut res = 0.0;

    for killed in necessary..=len {
        for killed_mask in (0u64..(1 << len)).filter(|x| x.count_ones() == killed as u32) {
            res += product_with_mask(probs.clone(), killed_mask);
        }
    }

    res
}

fn count_lucky_hunt_with_names<I, P>(probs: I, necessary: usize) -> f64
where
    I: IntoIterator<Item = P>,
    P: Borrow<(&'static str, f64)>,
    <I as IntoIterator>::IntoIter: ExactSizeIterator + Clone,
{
    count_lucky_hunt(probs.into_iter().map(|p| p.borrow().1), necessary)
}

#[test]
fn with_names() {
    let probs = [("медведь", 0.5), ("тигр", 0.5), ("лев", 0.5)];
    assert_eq!(count_lucky_hunt_with_names(&probs, 2), 0.5);
}

#[test]
fn some_variants() {
    let probs = [0.1, 0.5];
    assert_eq!(count_lucky_hunt(&probs, 1), 0.55);
    assert_eq!(count_lucky_hunt(&probs, 2), 0.05);
    assert_eq!(count_lucky_hunt(&probs, 3), 0.00);
}

#[test]
#[should_panic]
fn too_big() {
    let big = vec![0.5; SIZE_LIMIT + 1];
    count_lucky_hunt(&big, 4);
}