Задачка на количество сочетаний

Question

Условие

Вася пришёл на образовательный семинар и обнаружил, что зрителей на мероприятии — NN, а количество мест — MM. Помогите Васе определить вероятность того, что он попадёт на семинар.

Формат вывода

Два числа N и M.

Формат вывода

Два числа — количество вариантов, в которых Вася попадает на семинар и количество всех вариантов групп на семинаре.

Примечание

В первом примере обозначим участников числами 1, 2, 3. Предположим, что 1 — это Вася.

Тогда все вариации участников выглядят так:

А благополучными из них для Васи являются только 3:

1 2
1 3
1 4

Пример 1

Ввод: 4 2 Вывод: 3 6

Пример 2 Ввод: 10 3 Вывод: 36 120

Задачка из яндекс практикума. Мой код проходит 7 тестов, на 8 получает неправильный ответ. Какие именно там тесты неизвестно. Как можно сделать иначе? Я что-то упустил или не понял

import math
 
n, m = map(int, input().split())
k = math.comb(n, m)
print(int(k / n * m), k)

Answer 1

Интуитивная догадка (основанная на опыте), что если сначала делить, а потом умножать, то могут потеряться данные в каких-то далёких разрядах после запятой и округление сработает не так, как нужно - оказалась правильной. Ради интереса я даже поискал такие примеры:

import math

finish = 10
for n in range(1, 1_000_000):
    for m in range(1, n+1):
        k = math.comb(n, m)
        if int(k / n * m) != k * m // n or int(k / n * m) != int(k * m / n):
            print(f'{n=}, {m=}, {k=}')
            print(int(k / n * m), int(k * m / n), k * m // n)
            print(k / n * m, k * m / n, k * m // n)
            print('-'*20)
            finish -= 1
            break
    if not finish:
        break

Вывод:

n=33, m=27, k=1107568
906191 906192 906192
906191.9999999999 906192.0 906192
--------------------
n=35, m=25, k=183579396
131128139 131128140 131128140
131128139.99999999 131128140.0 131128140
--------------------
n=42, m=27, k=98672427616
63432274895 63432274896 63432274896
63432274895.99999 63432274896.0 63432274896
--------------------
n=44, m=22, k=2104098963720
1052049481859 1052049481860 1052049481860
1052049481859.9999 1052049481860.0 1052049481860
--------------------
n=49, m=21, k=39049918716424
16735679449895 16735679449896 16735679449896
16735679449895.998 16735679449896.0 16735679449896
--------------------
n=50, m=45, k=2118760
1906883 1906884 1906884
1906883.9999999998 1906884.0 1906884
--------------------
n=54, m=27, k=1946939425648112
973469712824055 973469712824056 973469712824056
973469712824055.9 973469712824056.0 973469712824056
--------------------
n=58, m=26, k=22150361247847371
9929472283517788 9929472283517788 9929472283517787
9929472283517788.0 9929472283517788.0 9929472283517787
--------------------
n=59, m=25, k=30284005485024837
12832205713993576 12832205713993576 12832205713993575
1.2832205713993576e+16 1.2832205713993576e+16 12832205713993575
--------------------
n=60, m=25, k=51915437974328292
21631432489303456 21631432489303456 21631432489303455
2.1631432489303456e+16 2.1631432489303456e+16 21631432489303455
--------------------

Как видно, это всё та же старая тема про неточность вычислений с плавающей точкой. До каких-то размеров чисел можно починить проблему, если переставить местами деление и умножение int(k * m / n), таким образом нивелируется неточность деления и преобразования в float, и это работает, но только до определённого момента, когда не хватает уже разрядов в типе float для представления больших целых чисел (последние два примера вывода). А вот если остаться целиком в поле целых чисел, используя только целочисленные операции k * m // n, то точность будет абсолютная, поскольку у питона тип int фактически бесконечный.

БЛОГ НА HUSL

Задачка на количество сочетаний

Ответы (1 шт):