1574. Бросание кубиков

Бросается n одинаковых игральных кубиков. Найти вероятность того, что сумма чисел на всех кубиках будет как минимум x.

Вход. Состоит из нескольких тестов. Каждый тест состоит из двух целых чисел n (1 ≤ n ≤ 24) и x (0 ≤ x < 150), смысл которых описан в условии задачи. Последний тест содержит n = 0, x = 0 и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести искомую вероятность в виде обыкновенной несократимой дроби в формате, указанном в примере. Все выводимые числа помещаются в беззнаковое 64-битовое целое.

Пример входа

3 9

1 7

24 24

15 76

24 56

24 143

23 81

7 38

0 0

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

20/27

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/6

1/36

2/36

3/36

4/36

5/36

6/36

5/36

4/36

3/36

2/36

1/36

1/216

3/216

6/216

10/216

15/216

21/216

25/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 - битовом беззнаковом целочисленном типе unsigned long long. Поскольку вычисления следует производить с дробями, определим тип рационального числа в структуре RatNumber. Определим рабочий массив res и дополнительные переменные.

struct RatNumber

{

unsigned long long x, y;

} one6, temp, res[25][150], s;

Для работы программы нам понадобятся функции вычисления наибольшего общего делителя (gcd) и наименьшего общего кратного (lcm).

unsigned long long gcd(unsigned long long a, unsigned long long b)

{

return (!b) ? a : gcd(b,a % b);

}

unsigned long long lcm(unsigned long long a, unsigned long long 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;

}