Будни браконьера

task110.go

package main

import "fmt"

// Перебираем все подходящие комбинации подстреленных животных и для каждой из них применяем правила сложения и
// умножения вероятностей.
// Всего комбинаций C(n, m), где m = k..n
// Например для комбинации [1, 3, 4] при n=6
// к результируещей вероятности прибавляем p1 * q2 * p3 * p4 * q5 * q6  (qi = 1 - pi).
// Для перебора комбинаций используются биты чисел. Если единиц < k, то пропускаем эту комбинацию.
// Если n-k > k, то переходим к обратной задаче.
// Если единиц > k, то пропускаем комбинацию.
// Вместо pi считаем qi и наоборот. Возвращаем 1 - рез. вероятность.
func task110(arr []float64, k int) float64 {
	var (
		n   = len(arr)
		res = 0.0

		// Мин. и макс. маски, для того, чтобы отсечь заведомо невернце варианты.
		// Например для n=6, k=3
		left    = 1<<uint(k) - 1 // 000111
		right   = 1<<uint(n) - 1 // 111111
		inverse = false
	)

	p := make([]float64, n)
	copy(p, arr)

	// Переход к обратной задаче. По бенчмарку решение с обр. задачей быстрее в 3 раза. Для проверки закоментируйте
	// этот блок.
	if n-k > k {
		// Например для n=6, k=5
		left = 0                                // 000000
		right = (1<<uint(k-1) - 1) << uint(n-k) // 111100 (k-1 ед. спереди)
		inverse = true

		// Изменяем вероятности на обратные у скопированного внутреннего слайса, чтобы не изменить внешние данные.
		for i := 0; i < n; i++ {
			p[i] = 1 - arr[i]
		}
	}

	for mask := left; mask <= right; mask++ {
		var (
			count = 0
			t     = 1.0
		)

		for j := 0; j < n; j++ {
			if mask&(1<<uint(j)) != 0 {
				t *= p[j]
				count++
			} else {
				t *= 1 - p[j]
			}
		}

		if inverse && count < k || !inverse && count >= k {
			res += t
		}
	}

	if inverse {
		return 1 - res
	}
	return res
}

func main() {
	cases := []struct {
		arr []float64
		k   int
	}{
		{[]float64{0.5, 0.5, 0.5}, 2},
		{[]float64{0.3, 0.4, 0.7, 0.1}, 2},
		{[]float64{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.2, 0.3, 0.4}, 19},
		{[]float64{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.2, 0.3, 0.4}, 1},
	}

	for _, c := range cases {
		fmt.Printf("arr: %v\nk: %d\nres: %.4f\n\n", c.arr, c.k, task110(c.arr, c.k))
	}
}

task110_test.go

package main

import "testing"

var cases = []struct {
	arr []float64
	k   int
}{
	{[]float64{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.2, 0.3, 0.4}, 19},
	{[]float64{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 0.2, 0.3, 0.4}, 1},
}

func BenchmarkBasic(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for j := range cases {
			task110(cases[j].arr, cases[j].k)
		}
	}
}

https://play.golang.org/p/PSAH2oJNJaa

Задача 110: Будни браконьера (решение будет в понедельник)
В диком заповеднике находятся редкие животные, всего N животных всех видов. Браконьеру нужно подстрелить не менее K животных, чтобы прокормить свою семью. Для каждого животного браконьер знает вероятность того, что он его подстрелит. Необходимо помочь браконьеру посчитать вероятность успеха охоты.

Входные данные: arr = (animal, probability) - массив ктр хранит пары: животное -> вероятность его подстрелить. K - минимальное кол-во животных, ктр необходимо подстрелить браконьеру.

Вывод: вероятность, что охота для браконьера окажется успешной.

Пример:
K = 2; arr = { "медведь", 0.5 }, { "тигр", 0.5 }, { "лев", 0.5 }
Answer = 0.5 (или 50%)