1573. Коровы и машины

В телевизионных конкурсах участников часто просят открыть одну или несколько дверей из заданного множества, за которыми находятся разные призы. В этой задаче мы будем иметь дело с одним из таких конкурсов. Итак, ведущий предложил Вам следующую игру:

Перед Вами находятся три двери. За двумя из них спрятаны коровы, а за третьей приз - автомобиль. После того как Вы выберете дверь, но еще не откроете ее, я дам Вам подсказку, открыв одну из дверей, за которой спрятана корова (я никогда не буду открывать дверь, выбранную Вами, даже если за ней находится корова). Вам следует принять решение - оставить Ваш выбор, или изменить его, выбрав одну из закрытых дверей. Вы выиграете то, что спрятано за дверьми.

Сложно поверить, но в этом примере вероятность выиграть автомобиль равна 2 / 3, если вы всегда будете менять свой выбор, когда ведущий будет давать возможность это сделать (после того как он покажет Вам дверь с коровой). Ответ 2 / 3 кроется в том, что если вы выбрали одну из двух коров, то после смены двери однозначно перейдете к машине, так как ведущий откроет Вам другую корову. Если вы изначально выбрали автомобиль, то перейдете к оставшейся корове и потеряете приз. Таким образом, в двух случаях из трех Вы выберете машину. Если вы решили не менять первоначальный выбор, то вероятность выигрыша, очевидно, составит только 1 / 3.

В этой задаче Вам следует вычислить вероятность выигрыша автомобиля, если входные данные немножко обобщены:

· Задается количество коров

· Задается количество автомобилей (число коров + число машин = общему количеству дверей)

· Задается количество дверей, открываемых ведущим (несколько дверей могут быть открытыми когда Вы решаете менять или не менять Ваш выбор)

Будем считать, что Вы всегда меняете свой выбор после того как ведущий откроет несколько дверей с коровами.

Вход. Содержит несколько тестов. Каждый тест состоит из одной строки, содержащей три целых числа: ncows (1 ≤ ncows ≤ 10000) – количество коров, ncars (1 ≤ ncars ≤ 10000) – количество дверей с машинами и nshow (0 ≤ nshow < ncows) – количество дверей, которое открывает ведущий перед тем как Вы будете менять свой выбор.

Выход. Для каждого теста вывести в отдельной строке вероятность выигрыша игрока, если после предложения ведущего он сменит свое мнение. Ответ выводить с 5 десятичными знаками.

Пример входа

2 1 1
5 3 2
2000 2700 900

Пример выхода

0.66667
0.52500

0.71056

РЕШЕНИЕ

вероятность

Анализ алгоритма

Для решения задачи следует записать формулу условной вероятности.

Число дверей равно doors = cows + cars. Вероятность сначала угадать корову составляет cows / doors, машину – cars / doors. После смены мнения и открытия дверей с shown коровами игрок может выбирать приз среди doors – shown – 1 закрытых дверей. Пусть вначале игрок указал на корову. Тогда среди закрытых дверей имеется cars машин, и вероятность ее выигрыша составляет

cars / (doors – shown – 1)

Если вначале игрок указал на машину, то среди закрытых дверей осталось cars – 1 машин и вероятность ее выигрыша составляет

(cars – 1) / (doors – shown – 1)

Результирующая вероятность выиграть машину равна

(cows / doors) * (cars / (doors – shown – 1)) + (cars / doors) * ((cars – 1) / (doors – shown – 1))

= (cows * cars + cars * (cars – 1)) / (doors * (doors – shown – 1)).

Пример

Рассмотрим первый тест. В игре имеются 3 двери. Если сначала игрок укажет на дверь с призом (вероятность 1/3), то после смены мнения он проиграет. Если сначала будет выбрана дверь с коровой (вероятность 2/3), то после открытия двери с коровой и смены мнения игрок непременно попадет на дверь с призом и выиграет. Таким образом, вероятность выигрыша составит 1/3 * 0 + 2/3 * 1 = 2/3.

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

Читаем входные данные, вычисляем чисто дверей doors, находим ответ по выше приведенной формуле и выводим его. Поскольку входные данные целые, то чтобы избежать потери точности при делении, следует делимое перевести в действительный тип, умножив его на 1.0.

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

{

doors = cows + cars;

res = 1.0*((cars-1)*cars + cars*cows)/(doors*(doors-shown-1));

printf("%.5lf\n",res);

}