Плюси й мінуси

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 4,00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type

Є ~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}~.


Коментарі

Please read the guidelines before commenting.


Ще немає коментарів.