Cows and Cars#1573

Cows and Cars (Editorial)

To solve the problem, use the law of total probability. Let us define:

$co w s$ — the number of doors hiding cows;
$c a r s$ — the number of doors hiding cars;
$d oor s = co w s + c a r s$ doors = cows + cars — the total number of doors;
$s h o w n$ — the number of doors hiding cows that the host opens.

Initially, the probability of choosing a door with a cow is $co w s / d oor s$ cows / doors, while the probability of choosing a door with a car is $c a r s / d oor s$ cars / doors.

After the player makes the initial choice, the host opens $s h o w n$ doors containing cows. The player then switches their choice and selects one of the remaining closed doors.

After opening $s h o w n$ doors and excluding the door initially chosen by the player, there are $d oor s - s h o w n - 1$ doors - shown - 1 closed doors remaining. Let us consider two cases.

1. The player initially chooses a cow.

The probability of this event is $co w s / d oor s$ cows / doors.

Since all doors opened by the host contain cows, all $c a r s$ are among the remaining closed doors. Therefore, the probability of choosing a car after switching is

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

cars / (doors - shown - 1)

Therefore, the contribution of this case to the overall probability is the product of the probability of initially choosing a cow and the probability of subsequently choosing a car.

2. The player initially chooses a car.

The probability of this event is $c a r s / d oor s$ cars / doors.

After the host opens $s h o w n$ doors containing cows, there are $c a r s - 1$ cars - 1 cars among the remaining closed doors, since one car is already behind the door initially chosen by the player. Therefore, the probability of choosing a car after switching is

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

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

Therefore, the contribution of this case to the overall probability is the product of the probability of initially choosing a car and the probability of choosing a car again after switching.

Thus, the resulting probability of winning a car is calculated as the sum of the probabilities of winning in these two cases:

\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)}

Example

Let us consider the first sample test case. There are three doors in the game.

If the player initially chooses the door with the prize, the probability of making this choice is $1/3$ . After switching their choice, the player will definitely lose, since the only remaining closed door leads to a cow.

If, however, the player initially chooses a door with a cow, the probability of making this choice is $2/3$ . The host opens the other door containing a cow, and after switching their choice, the player will definitely choose the door with the prize and win.

Therefore, the overall probability of winning is

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

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

Algorithm implementation

Read the input data.

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

Calculate the number of doors $d oor s$ .

  doors = cows + cars;

Calculate the answer using the formula and print it.

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