Ś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.