Knockout to gra w koszykówkę, w której gracze na zmianę strzelają. Rozgrywka jest sekwencją dwóch graczy, z których każdy ma możliwość „znokautowania” jednego z tych graczy.
Załóżmy, że gracze mają odpowiednio A B C D
swoje szanse na strzelanie i zrobienie kosza 0.1 0.2 0.3 0.4
, niezależnie od drugiego gracza biorącego udział w konkursie. Dwóch graczy z przodu linii A
i B
„walczyć”. Ponieważ A
idzie pierwszy, jest on obrońcą , grozi wyeliminowane, a B
to napastnik , a nie w niebezpieczeństwie natychmiastowej eliminacji. A
najpierw strzela. Jeśli A
to zrobi, A
skutecznie się bronił i idzie na koniec linii. Linia zmieni się na B C D A
. Jeśli się A
nie uda , to B
strzela. Jeśli B
to zrobi, wtedy A
jest na zewnątrz i B
przechodzi na koniec linii, więc linia staje się C D B
. Jeśli nieA
nie B
czyni go powtórzenia procesu, ze A
strzelanie ponownie, dopóki albo A
czy B
sprawia kosz.
Załóżmy, że linia zmieniła się na B C D A
( A
udało się obronić). Teraz B
i C
„walcz”, B
będąc obrońcą i C
atakującym. Ten proces powtarza się, aż pozostanie tylko jedna osoba. Ta osoba jest zwycięzcą.
Twoim zadaniem jest obliczenie prawdopodobieństwa wygranej przez każdą osobę, biorąc pod uwagę szansę, że zrobi ona koszyk.
Wejście :
Lista liczb, takich jak 0.1 0.2
lub 0.5 0.5 0.5 0.5
, gdzie n- ta liczba to szansa, że n- ty gracz zrobi koszyk. Możesz wziąć to wejście w dowolnym formacie, w tym jako parametrach funkcji.
Wyjście :
Lista liczb, gdzie n- ta liczba to szansa, że n- ty gracz wygra grę. Twoje liczby muszą być dokładne z dokładnością do co najmniej dwóch miejsc po przecinku przez co najmniej 90% czasu. Oznacza to, że możesz zastosować podejście oparte na symulacji. Jeśli jednak kod nie jest oparty na symulacji ( gwarantuje poprawną odpowiedź co najmniej 6 miejsc po przecinku), odejmij 30% od wyniku.
Przykład pomiędzy 0.5 0.5
: Zadzwoń do graczy A
i B
. Niech p
będzie prawdopodobieństwo wygranej A. A
ma 2/3
szansę na skuteczną obronę (ponieważ istnieje 1/2
szansa, że A
zdobędzie punkty, 1/4
szansa, że A
nie trafi i B
zdobędzie punkty, a także 1/4
szansa, że zarówno nie trafi , jak i proces się powtórzy). Jeśli się A
nie obroni, zostaje znokautowany i B
wygrywa. Jeśli się A
broni, linia staje się B A
. Ponieważ sytuacja jest symetryczna, prawdopodobieństwo A
wygranej jest (1 - p)
. Otrzymujemy:
p = 2/3 * (1 - p) + 1/3 * 0
. Dostajemy rozwiązanie p = 2/5
. Dane wyjściowe powinny być 2/5 3/5
lub 0.4 0.6
.
Z prawdopodobieństwem nie jestem w stanie zrobić bardziej złożonych przykładów.
Jeśli potrzebujesz więcej przypadków testowych, oto kilka:
0.1 0.2 0.3 0.4 --> 0.01 0.12 0.25 0.62
0.99 0.99 --> 0.5 0.5 (it's not exact, but if you round to two decimal places, you get 0.5 and 0.5)
źródło