809. Квадратные и круглые
Слышу,
брат, что будет война,
Холодная,
мокрая, длинная, злая.
Квадратные
на Круглых будут идти
За то
что те ровные, как не крути.
Ансамбль
"Скрябин"
Вождь
Квадратных, находясь в состоянии аффекта, выдал каждому из своих бойцов настолько
большую дозу Озверина, что каждый из них сначала нападает, а потом уже
разбирается, напал он на Квадратного или Круглого. Круглые же никогда не умели
воевать врукопашную, но они владеют некоторыми магическими приемами.
Итак, отряд из s Квадратных напал на посёлок, в котором
жили r Круглых. Вследствие наложения
действия Озверина и магических приёмов Круглых, оказалось, что бой происходит
по таким правилам. Ежеминутно случайно выбирается пара существ, и:
·
если выбраны Круглый и Квадратный, то
Квадратный убивает Круглого и воюет дальше;
·
если выбраны два Круглых, они просят
друг у друга прощения и воюют дальше;
·
если выбраны два Квадратных, они убивают
друг друга.
Пара выбирается
случайно и равновероятно среди всех живых так, чтобы встретились два разных
существа (возможно, одного вида). Например, когда живы два Квадратных и один
Круглый, то с одинаковыми вероятностями 1/3 состоится или стычка 1-го
Квадратного и Круглого, или 2-го Квадратного и Круглого, или 1-го и 2-го
Квадратных. В первых двух случаях побеждает Квадратный, а в третьем - погибнут Квадратные.
Напишите
программу, которая найдет вероятность того, что при соблюдении данных правил
боя хотя бы один Круглый выживет, а все Квадратные погибнут.
Вход. В единственной строке содержится два
числа – количество Квадратных s (1
≤ s ≤ 2010) и количество
Круглых r (1 ≤ r ≤ 2010).
Выход. Вывести
одно число – искомую вероятность (с относительной погрешностью не более 10-9).
|
Пример входа |
Пример выхода |
|
2 20 |
0.80545497225 |
РЕШЕНИЕ
динамическое
программирование + теория вероятности
Анализ алгоритма
Из условия задачи следует, что квадратные могут погибать только парами.
Следовательно если s нечетно, то ответ равен 0.
Обозначим через p(s,
r) вероятность того, что все Квадратные погибнут, а хотя бы один
Круглый выживет. Очевидно, что p(s, 0) = 0 при любом s ≥ 0 и p(0, r) = 1 при любом r ≥ 1.
Пусть на данный момент живы s Квадратных и r Круглых.
Тогда из них можно выбрать 
= 
пар. Из этого
количества s * r приходится на пары «Круглый - Квадратный», 
= 
на пары «Квадратный -
Квадратный» и 
= 
на пары «Круглый -
Круглый». По формуле полной вероятности получим:
p(s, r) = 
+ 
+ 
Помножим равенство на и сведем подобные:
p(s, r) 
= 
+ 
или то же самое что
p(s, r) = 
Пример
Рассмотрим тест, в котором s =
2, r = 1. Для вычисления p(2, 1) нам потребуются p(2, 0) и p(0, 1). Заметим, что p(2,
0) = 0 и p(0, 1) = 1.Тогда
p(2, 1) = 
= 
= 
Реализация алгоритма
Рекурсивная
реализация алгоритма не пройдет по времени, следует писать циклическую. В ячейках
массива res[i][j] будем хранить значение вероятности p(i, j).
#define MAX 2011
#define EPS 1e-7
double res[MAX][MAX];
Основная часть программы. Читаем входные данные.
Инициализируем res[i][0] = 0
при i ≥ 0 и res[0][j] = 1 при j ≥ 1.
scanf("%d %d",&s,&r);
memset(res,0,sizeof(res));
for(i = 1; i < MAX; i++) res[0][i]
= 1;
Пересчитываем значения res[i][j]
согласно формуле, указанной в объяснении задачи.
for(i = 1; i <= s; i++)
for(j = 1; j <= r; j++)
{
res[i][j] = 2 * i * j * res[i][j-1] +
i * (i - 1) * ((i > 1) ?
res[i-2][j] : 0);
res[i][j] /= ((i + j) * (i + j - 1) - j * (j
- 1));
}
Выводим ответ.
printf("%.11lf\n",res[s][r]);