| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 2048 MB | 3 | 3 | 3 | 100.000% |
Marysia podchodzi do egzaminu składającego się z $n$ pytań. Odpowiedź na każde pytanie oceniana jest następująco:
Żeby zdać egzamin, trzeba zdobyć co najmniej $t$ punktów.
Dla każdego pytania Marysia ustaliła potencjalną odpowiedź, ale nie zawsze jest pewna, czy jest ona poprawna. Dokładniej, dla $i$-tego pytania wie, że odpowiedź jest poprawna z prawdopodobieństwem $p_i$. Poprawność odpowiedzi dla różnych pytań to zdarzenia niezależne.
Marysia musi wybrać, na które pytania udzielić odpowiedzi, a które zostawić bez odpowiedzi, żeby zmaksymalizować prawdopodobieństwo zdania egzaminu.
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n,ドル $t$ (1ドル ≤ t ≤ n ≤ 50,円 000$): liczba pytań i wymagana minimalna liczba punktów.
W kolejnych $n$ wierszach znajdują się prawdopodobieństwa poprawności odpowiedzi: $i$-ty z tych wierszy zawiera liczbę rzeczywistą $p_i$ (0ドル ≤ p_i ≤ 1$), która ma co najwyżej 9ドル$ cyfr po kropce dziesiętnej.
W jedynym wierszu wyjścia powinna znaleźć się jedna liczba rzeczywista: prawdopodobieństwo, że Marysia zda egzamin, jeśli optymalnie wybierze, na które pytania udzielić odpowiedzi. Liczba musi być wypisana w postaci dziesiętnej (nie wykładniczej) z co najwyżej 20ドル$ miejscami po przecinku.
Maksymalny dopuszczalny błąd bezwzględny to 10ドル^{-6}$.
5 2 0.77 0.85 0.75 0.98 0.6
0.8798125
5 3 0.3 0.01 0.2 0.15 0
0.009
3 3 0.000001 0.000001 0.000001
0
Wyjaśnienie przykładów: W pierwszym przykładzie optymalną strategią jest odpowiedzieć na pierwsze 4ドル$ pytania, a ostatnie zostawić bez odpowiedzi. W ten sposób nawet przy jednej błędnej odpowiedzi Marysia uzyska 2ドル$ punkty.
W drugim przykładzie optymalną strategią jest odpowiedzieć na pierwsze, trzecie i czwarte pytanie. Marysia uzyska 3ドル$ punkty, jeśli wszystkie te odpowiedzi będą poprawne. Ponieważ te zdarzenia są niezależne, prawdopodobieństwo wynosi 0,3ドル \cdot 0,2 \cdot 0,15 = 0,009$.
W ostatnim przykładzie prawdopodobieństwo sukcesu to 10ドル^{-18},ドル możemy je zaokrąglić do 0ドル$.
Contest > Algorithmic Engagements > PA 2025 2-3번