Плюси й мінуси
Перегляд у форматі PDFЄ ~a~ карток, на яких написано +, та ~b~ карток, на яких написано –; ці написи є лише з одного боку, а з іншого боку ці картки (всі ~a+b~ штук) однакові. Всі ці картки якось випадково перемішані, й усі лежать догори тією стороною, з якої вони однакові.
Єдиний гравець може брати ці картки по одній, перевертати й дивитися, чи взяв +, чи –. За кожну картку, на якій написано +, виграш гравця збільшується на 1, а за кожну, на якій написано –, зменшується на 1, і може ставати від'ємним. Зокрема, якщо забрати всі картки, то виграш буде ~a-b~.
Але гравець не зобов'язаний забирати всі картки; він має право в будь-який момент (після взяття будь-якої картки, вже побачивши її позначку, або на самому початку, ще нічого не взявши) заявити «закінчую» і припинити гру. Тоді його виграш дорівнює сумі, яку він уже набрав на той момент (включно з останньою взятою карткою, якщо така була).
Яке максимальне матсподівання виграшу може забезпечити собі гравець при правильній грі?
Вхідні дані
У єдиному рядку через пропуск (пробіл) вказано два числа ~a~, ~b~ (обидва цілі, з проміжку від 0 до 100) – кількості карток з позначками + та – відповідно.
Вихідні дані
Виведіть єдине дійсне число – матсподівання виграшу для найкращої можливої стратегії єдиного гравця, якщо картки перемішані випадково, а гравець знає числа ~a~, ~b~. Формат виведення може бути будь-яким зі стандартних (зокрема, байдуже, чи вивести 0.5, чи 0.500000000, чи 5e-1), важливо лише забезпечити точність, вказану в «Оцінюванні».
Приклади
Ввід
2 0
Вивід
2
Ввід
0 2
Вивід
0
Ввід
7 50
Вивід
0
Ввід
1 1
Вивід
0.5
Ввід
7 9
Вивід
0.299038462
Примітки
У першому прикладі, всі картки мають позначки +, їх вигідно забрати всі (обидві).
У другому прикладі, всі картки мають позначки –, їх вигідно взагалі не брати.
У третьому прикладі, мінусів настільки більше, чим плюсів, що теж вигідно взагалі не брати.
У четвертому прикладі, вигідно взяти першу картку, далі так:
- якщо на ній
+, то спинитися; виграш буде 1; - якщо на ній
–, то взяти й наступну (останню), на ній точно буде+; виграш буде ~{({-}1)\,{+}\,1}{{=}}0~.
Ймовірності кожного з цих випадків ~\frac{1}{2}~, тому матсподівання ~{\frac{1}{2}\cdot1}{{+}}{\frac{1}{2}\cdot0}{{=}}{\frac{1}{2}}{{+}}{0}{{=}}{\frac{1}{2}}~. Також зверніть увагу, що міркування «раз плюсів і мінусів однаково, то й сума буде 0», хоч і може здатися природнім, насправді нічого не дає в цій задачі. Саме тому, що в деяких ситуаціях вигідніше зупинитися й не забирати решту карток.
П'ятий приклад надто громіздкий, щоб пояснити число-відповідь детально; але зверніть увагу, що вміння вчасно зупинятися може дати додатне матсподівання виграшу, навіть коли мінусів (трохи) більше, чим плюсів.
Оцінювання
Потестове (кожен тест перевіряють і оцінюють незалежно від решти). Тест зараховують, коли абсолютна або відносна похибка (хоча б одна з двох) не перевищує ~10^{-9}~.
Коментарі