Разберём сразу две задачки, потому что там одинаковые рассуждения формулы. Читаем условия:
Разбор начнём с первой задачи, но писать код будем сразу для второй, потому что первая - это подзадача второй, и я думаю, что вы сможете самостоятельно выкинуть лишнее.
Без потери общности будем считать, что выиграла первая команда (если это не так, то всегда можем поменять местами). Рассмотрим на примере, когда синяя команда выиграла со счётом 25:7.
Если нарисовать в ряд порядок, в котором команды набирали очки, то получится что-то похожее на рисунок сверху. Если бы команды набирали очки в другом порядке (но синяя команда всё ещё выиграла с тем же счётом), тогда синие и красные квадратики были в другом порядке. Лишь последний квадрат всегда останется синим, потому что последний розыгрыш всегда за выигравшей командой (иначе она выиграла на предыдущем шаге).
А это значит, что нужно посчитать количество способов выбрать 7 элементов из 31 (25 + 7 - 1). Для этого в комбинаторике есть формула - число сочетаний:
Можно сразу написать функцию, которая вычисляет число сочетаний, она полезная и используется во многих задачах:
Замечу, что в реализации числитель и знаменатель вычисляются не по отдельности, а всё значение сразу. Тут есть один момент - целочисленное деление, которое потенциально может приводить к округлению, но этого не будет, потому что множители в знаменателе начинаются с 1 (на неё можно смело делить). А когда цикл дойдёт до множителя i, то в числителе уже будет произведение i последовательных чисел (а среди них обязательно есть число, которое делится на i без остатка).
Отдельным случаем являются партии, которое перешли в фазу "больше-меньше", потому что после счёта 24:24 красные квадраты не могут располагаться в произвольном порядке.
Так, чтобы партия продолжалась до счёта 30:28 необходимо, чтобы в каждой паре розыгрышей каждая команда взяла по одному, и только в последнем выигравшая команда берёт оба розыгрыша. А так как в каждой паре порядок выигрыша неважен, то с каждой такой парой розыгрышей количество различных партий удваивается:
Теперь можно и писать код. Считаем данные:
Так как пятая партия отличается от всех предыдущих тем, что идёт до 15, все рассуждения надо повторить, чуть-чуть изменятся формулы, но смысл останется прежним, поэтому можно всё обработать одним циклом:
В цикле сразу поменяли местами компоненты счёта, если оказалось, что вторая команда набрала больше. В f будет храниться число, до которого идёт партия. Тогда вычисление ответа разделится на два случая:
Этот фрагмент, по сути, является решением первой задачи.
А теперь выводим ответ:
Математика, длинная арифметика в Python и 19 строчек кода принесли нам 124 баллов в рейтинге.
Предыдущий выпуск: Задача 155. Конденсаторы
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
