Корови та машини#1573

Корови та машини (Розбір)

Для розв'язання задачі скористаємося формулою повної ймовірності. Позначимо:

$co w s$ — кількість дверей з коровами;
$c a r s$ — кількість дверей з автомобілями;
$d oor s = co w s + c a r s$ doors = cows + cars — загальна кількість дверей;
$s h o w n$ — кількість дверей з коровами, які відкриває ведучий.

Спочатку ймовірність вибрати двері з коровою дорівнює $co w s / d oor s$ cows / doors, а ймовірність вибрати двері з автомобілем дорівнює $c a r s / d oor s$ cars / doors.

Після того як гравець зробив первинний вибір, ведучий відкриває $s h o w n$ дверей з коровами. Потім гравець змінює свій вибір і обирає одні з дверей, що залишилися закритими.

Після відкриття $s h o w n$ дверей і виключення первинно обраних дверей залишається $d oor s - s h o w n - 1$ doors - shown - 1 закритих дверей. Розглянемо два випадки.

1. Спочатку гравець обрав корову.

Ймовірність цієї події дорівнює $co w s / d oor s$ cows / doors.

Оскільки всі відкриті ведучим двері містять корів, серед дверей, що залишилися закритими, знаходяться всі $c a r s$ автомобілів. Тому ймовірність обрати автомобіль після зміни вибору дорівнює

c a r s / (d oor s - s h o w n - 1)

cars / (doors - shown - 1)

Отже, внесок цього випадку в підсумкову ймовірність дорівнює добутку ймовірності первинно обрати корову та ймовірності потім обрати автомобіль.

2. Спочатку гравець обрав автомобіль.

Ймовірність цієї події дорівнює $c a r s / d oor s$ cars / doors.

Після відкриття $s h o w n$ дверей з коровами серед дверей, що залишилися закритими, знаходиться $c a r s - 1$ cars - 1 автомобілів, оскільки один автомобіль вже знаходиться за первинно обраними дверима. Тому ймовірність обрати автомобіль після зміни вибору дорівнює

(c a r s - 1) / (d oor s - s h o w n - 1)

(cars - 1) / (doors - shown - 1)

Отже, внесок цього випадку в підсумкову ймовірність дорівнює добутку ймовірності первинно обрати автомобіль та ймовірності знову обрати автомобіль після зміни вибору.

Таким чином, результуюча ймовірність виграшу автомобіля обчислюється як сума ймовірностей виграшу в цих двох випадках:

\frac{co w s}{d oor s} \cdot \frac{c a r s}{d oor s - s h o w n - 1} + \frac{c a r s}{d oor s} \cdot \frac{c a r s - 1}{d oor s - s h o w n - 1} = = \frac{co w s \cdot c a r s + c a r s \cdot ( c a r s - 1 )}{d oor s \cdot ( d oor s - s h o w n - 1 )}

\frac{cows}{doors} \cdot \frac{cars}{doors-shown-1} + \frac{cars}{doors} \cdot \frac{cars-1}{doors-shown-1} = \\ = \frac{cows \cdot cars + cars \cdot (cars - 1)}{doors \cdot (doors - shown - 1)}

Приклад

Розглянемо перший тестовий приклад. У грі є троє дверей.

Якщо спочатку гравець обирає двері з призом, то ймовірність такого вибору становить $1/3$ . Після зміни вибору він обов'язково програє, оскільки двері, що залишилися закритими, ведуть до корови.

Якщо ж спочатку гравець обирає двері з коровою, то ймовірність такого вибору становить $2/3$ . Ведучий відкриває інші двері з коровою, і після зміни вибору гравець обов'язково обирає двері з призом і виграє.

Таким чином, підсумкова ймовірність виграшу дорівнює

1/3 \cdot 0 + 2/3 \cdot 1 = 2/3

1/3 \cdot 0 + 2/3 \cdot 1 = 2/3

Реалізація алгоритму

Читаємо вхідні дані.

while(scanf("%d %d %d",&cows,&cars,&shown) == 3)
{

Обчислюємо кількість дверей $d oor s$ .

  doors = cows + cars;

Обчислюємо відповідь за формулою та виводимо її.

  res = 1.0*((cars - 1)*cars + cars*cows)/(doors*(doors – shown - 1));
  printf("%.5lf\n",res);
}