Ślepy Nim
Limit pamięci: 32 MB
Sprague i Grundy bawili się, grając w grę Nim.
Na początku kładli na stole stosów żetonów.
W trakcie gry wykonywali ruchy na przemian.
W każdej turze gracz wybierał jeden stos i zabierał z niego dowolną dodatnią liczbę żetonów.
Przegrywał ten zawodnik, który nie mógł wykonać poprawnego ruchu.
Sprague i Grundy szybko znaleźli optymalną strategię w tej grze, dlatego postanowili spróbować czegoś ciekawszego.
Zdecydowali, że będą grać w ciemno, to znaczy nie będą znali dokładnej liczby żetonów na stosach w momencie rozpoczęcia gry.
Dowiedzą się jedynie, że początkowo liczba żetonów w -tym stosie jest wylosowana z przedziału ,
przy czym szansa wylosowania każdej (całkowitej) liczby z tego przedziału jest taka sama; liczby żetonów w poszczególnych stosach są losowane niezależnie.
Grę przegrywa ten z graczy, który spróbuje wziąć ze stosu więcej żetonów, niż jest aktualnie na stosie.
W szczególności, jeśli gracz wie, że wszystkie stosy muszą być puste, to musi i tak spróbować wykonać ruch i przegrać.
Pierwszy ruch wykonuje Sprague.
Jakie jest prawdopodobieństwo jego wygranej, jeśli zakładamy, że obaj zawodnicy
grają optymalnie i w trakcie rozgrywki widzą wzajemnie swoje ruchy?
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita (), oznaczająca liczbę stosów.
Drugi wiersz zawiera ciąg dodatnich liczb całkowitych , których suma nie przekracza .
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę rzeczywistą
- prawdopodobieństwo wygrania gry przez Sprague'a.
Liczba ta może różnić się od faktycznego wyniku o co najwyżej .
Po kropce dziesiętnej nie powinno znajdować się więcej niż 20 cyfr.
Przykład
Dla danych wejściowych:
3
1 1 1
poprawną odpowiedzią jest:
0.375
Autor zadania: Tomasz Idziaszek.