In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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?
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
.
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.
Dla danych wejściowych:
3 1 1 1
poprawną odpowiedzią jest:
0.375
Autor zadania: Tomasz Idziaszek.