10759. Подбрасывание кубиков
Подбрасывается n кубиков.
Вычислить вероятность того, что сумма очков на всех кубиках будет как минимум х.
Вход. Каждая строка является отдельным
тестом и содержит два целых числа: n
(1 £ n £ 24) и x (0 £ x < 150). Последний тест содержит n = x = 0 и не обрабатывается.
Выход. Для каждого теста вывести вероятность
того, что сумма очков на всех кубиках будет как минимум х в формате, приведенном в
примере. Все числа в ответе помещаются в беззнаковый 64 – битовый тип.
Пример входа
3 9
1 7
24 24
15 76
24 56
24 143
23 81
7 38
0 0
Пример выхода
20/27
0
1
11703055/78364164096
789532654692658645/789730223053602816
25/4738381338321616896
1/2
55/46656
РЕШЕНИЕ
вероятность
Анализ алгоритма
Учитывая ограничения на n и x,
вычислим в ячейках массива res[i][j] вероятность того, что при бросании в
точности i кубиков выпадет сумма j. Очевидно, что при бросании одного
кубика вероятность выпадения любого значения от 1 до 6 одинакова и равна 1/6:
res[1][i] = 
При бросании i кубиков может выпасть сумма j, если при бросании первых i – 1 кубиков выпадет сумма j – k, а при бросании i - ого кубика сумма k, k
= 1, 2, …, 6. Таким образом
res[i][j]
= res[i – 1][j – 6] * res[1][6] +
+ res[i – 1][j – 5] * res[1][5] + … + res[i
– 1][j – 1] * res[1][1] =
= 
,
учитывая
что res[1][6] = res[1][5] = … = res[1][1] = 1/6.
Вероятность того, что сумма очков
при бросании n кубиков будет как
минимум х, равна
s = 
Пример
Рассмотрим пример заполнения массива
res для одного, двух и трех кубиков. В пустых клетках вероятность равна 0.
|
i/j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
1 |
1/6 |
1/6 |
1/6 |
1/6 |
1/6 |
1/6 |
|
|
|
|
|
|
|
2 |
|
1/36 |
2/36 |
3/36 |
4/36 |
5/36 |
6/36 |
5/36 |
4/36 |
3/36 |
2/36 |
1/36 |
|
3 |
|
|
1/216 |
3/216 |
6/216 |
10/216 |
15/216 |
21/216 |
25/216 |
27/216 |
27/216 |
25/216 |
Обозначим через P(n = i,
s = j) вероятность того, что при бросании n кубиков выпадет сумма j.
Рассмотрим вычисление значений некоторых ячеек.
а) На двух кубиках сумма 5 может получиться при следующих исходах: 1 + 4, 2
+ 3, 3 + 2, 4 + 1. То есть
P(n = 2, s = 5) = P(n = 1, s = 1) * P(n = 1, s = 4) + P(n = 1, s = 2) * P(n = 1, s = 3) +
+ P(n = 1, s = 3) * P(n = 1, s = 2) + P(n = 1, s = 4) * P(n = 1, s = 1) =
= 1/6 * 1/6 + 1/6 * 1/6 + 1/6 *
1/6 + 1/6 * 1/6 = 4/36
б) На трех кубиках может получиться сумма 10, если на первых двух выпало 4,
на третьем – 6, или на первых двух 5, на третьем 5 и так далее. При этом значения
вероятностей для двух кубиков P(n =
2, s = i) уже вычислены.
P(n = 3, s = 10) = P(n = 2, s = 4) * P(n = 1, s = 6) + P(n = 2, s = 5) * P(n = 1, s = 5) +
+ P(n = 2, s = 6) * P(n = 1, s = 4) + P(n = 2, s = 7) * P(n = 1, s = 3) +
+ P(n = 2, s = 8) * P(n = 1, s = 2) + P(n = 2, s = 9) * P(n = 1, s = 1) =
= 3/36 * 1/6 + 4/36 * 1/6 + 5/36
* 1/6 + 6/36 * 1/6 + 5/36 * 1/6 + 5/36 * 1/6 =
= 3/216 + 4/216 + 5/216 + 6/216 +
5/216 + 4/216 = 27/216
Реализация алгоритма
Все вычисления будем проводить в
64 – битовом целочисленном типе long long. Переопределим его.
#define i64 long
long
Поскольку вычисления следует производить с дробями,
определим тип рационального числа в структуре RatNumber. Определим рабочий
массив res и дополнительные переменные.
struct RatNumber
{
i64 x,y;
} one6,temp,res[25][150],s;
Для работы программы нам понадобятся функции вычисления
наибольшего общего делителя (gcd) и наименьшего общего кратного (lcm).
i64 gcd(i64 a, i64
b)
{
return (!b) ?
a : gcd(b,a % b);
}
i64 lcm(i64 a,
i64 b)
{
return a /
gcd(a,b) * b;
}
Функция RatNumber складывает два рациональных числа по
формуле
= 
Вычисляя наименьшее общее кратное знаменателей, можно
избежать переполнения. Далее находим наибольший общий делитель числителя и
знаменателя результата и сокращаем полученную сумму.
struct RatNumber add(struct RatNumber a,struct
RatNumber b)
{
struct
RatNumber res;
res.y = lcm(a.y,b.y);
res.x = res.y/a.y*a.x + res.y/b.y*b.x;
d = gcd(res.x,res.y);
if (d)
{
res.x
/= d;res.y /= d;
}
return res;
}
Основная часть программы. Установим значения рациональных
чисел res[i][j] равными 0, интерпретируя 0 как 0/1.
int main(void)
{
for(i=0;i<25;i++)
for(j=0;j<150;j++)
res[i][j].x = 0, res[i][j].y = 1;
Определим рациональное число one6 = 1/6 и инициализируем
им значения res[1][i], i = 1, 2, …, 6.
one6.x = 1; one6.y = 6;
for(i=1;i<=6;i++)
res[1][i] = one6;
Вычисляем значения res[i][j] по выше приведенной рекуррентной
формуле.
for(n=2;n<25;n++)
for(i=n-1;i<=6*(n-1);i++)
for(j=1;j<=6;j++)
{
temp = res[n-1][i];
temp.y = temp.y*6;
res[n][i+j] = add(res[n][i+j],temp);
}
Для
каждой пары входных значений n и x находим вероятность того, что сумма очков на всех
кубиках будет как минимум х. Для
этого вычисляем сумму
s =
while(scanf("%d %d",&n,&x),n+x)
{
s.x = 0, s.y = 1;
for(i = x;
i <= 6*n; i++)
s = add(s,res[n][i]);
Выводим искомую вероятность в виде дроби. Если результат
равен 0, то выводим один 0. Если вероятность равна 1, то выводим 1.
if (s.x ==
0) printf("0\n"); else
if (s.y ==
1) printf("%lld\n",s.x); else
printf("%lld/%lld\n",s.x,s.y);
}
return 0;
}