0

Условие

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

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

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

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

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

Примечание

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

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

1 2
1 3
1 4
2 3
2 4
3 4

А благополучными из них для Васи являются только 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)
5
  • Чисто интуитивно - попробуйте поменять умножение и деление местами. Не факт, что поможет, но вдруг. Хотя вряд ли.
    – CrazyElf
    13 дек 2022 в 7:31
  • @CrazyElf не прошло
    – vyacheslav
    13 дек 2022 в 7:35
  • @CrazyElf print(k * m // n, k) вот так принял :D
    – vyacheslav
    13 дек 2022 в 8:06
  • Очень интересно ))
    – CrazyElf
    13 дек 2022 в 8:21
  • Только не удаляйте вопрос, хотя это вариация на старую тему неточности вычислений с плавающей точкой, но что-то меня пробило на очередное исследование на тему )
    – CrazyElf
    13 дек 2022 в 8:36

1 ответ 1

2

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

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 фактически бесконечный.

1
  • 1
    блин, это прям целое исследование на тему, о которой я и не задумывался. Это классно и полезно! +rep
    – vyacheslav
    13 дек 2022 в 10:02

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.