CF 105206A - Захар и скины

CF 105206A - \u0417\u0430\u0445\u0430\u0440 \u0438 \u0441\u043a\u0438\u043d\u044b

Rating: -
Tags: -
Solve time: 58s
Verified: yes

Solution

Problem Understanding

Захар имеет n различных скинов и хочет выбрать ровно k из них. Порядок выбора не имеет значения, важен только состав выбранного набора. Нужно посчитать, сколько различных наборов из k скинов можно получить.

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

Ограничения очень маленькие, n не превышает 20. Это означает, что даже полный перебор всех подмножеств из 2^20 = 1 048 576 вариантов вполне возможен. При этом существует еще более простое математическое решение, поскольку задача сводится к вычислению биномиального коэффициента.

Есть несколько ситуаций, которые легко реализовать неверно.

Если k = 1, каждый отдельный скин образует свой собственный набор.

Ввод:

2 1

Ответ:

Ошибка возникает, если считать перестановки вместо сочетаний.

Если k = n, выбрать можно только все скины сразу.

Ввод:

3 3

Ответ:

Некоторые реализации формулы могут ошибиться из-за неверных границ цикла и получить 0 или другое неправильное значение.

Еще один случай связан с вычислением факториалов. Например,

20 10

Ответ равен:

При использовании вещественной арифметики возможно накопление ошибок округления. Лучше выполнять вычисления только с целыми числами.

Approaches

Самый прямой способ состоит в переборе всех подмножеств множества из n элементов. Для каждого подмножества можно подсчитать количество выбранных элементов и увеличить ответ, если их ровно k. Такой алгоритм абсолютно корректен, поскольку рассматривает каждый возможный набор ровно один раз. При максимальном n придется проверить 2^20 = 1 048 576 масок, что также укладывается в ограничения.

Однако сама задача просит лишь посчитать количество способов выбора. Перебирать сами наборы необязательно, поскольку это классическое число сочетаний.

Количество способов выбрать k элементов из n равно

$$C(n,k)=\frac{n!}{k!(n-k)!}.$$

Так как n не больше 20, факториалы легко помещаются в целые числа Python, а сама формула вычисляется практически мгновенно.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n)	O(1)	Accepted
Optimal	O(n)	O(1)	Accepted

Algorithm Walkthrough

Считать значения n и k.
Вычислить n!. Для этого последовательно перемножить числа от 1 до n.
Аналогично вычислить k!.
Аналогично вычислить (n-k)!.
Подставить полученные значения в формулу биномиального коэффициента и выполнить целочисленное деление.
Вывести результат.

Why it works

Биномиальный коэффициент по определению равен числу различных подмножеств размера k среди n различных элементов. Факториал n! считает все возможные перестановки элементов, а деление на k! и (n-k)! устраняет различия, возникающие только из-за изменения порядка внутри выбранной и невыбранной частей. После этого остается ровно количество различных наборов.

Python Solution

import sys
input = sys.stdin.readline

def fact(x):
    res = 1
    for i in range(2, x + 1):
        res *= i
    return res

n, k = map(int, input().split())

ans = fact(n) // (fact(k) * fact(n - k))
print(ans)

Функция fact вычисляет факториал обычным циклом. Поскольку максимальное значение равно 20, выполнение занимает всего несколько десятков операций.

После чтения входных данных вычисляются три необходимых факториала. Используется целочисленное деление //, так как биномиальный коэффициент всегда является целым числом.

Python автоматически поддерживает целые числа произвольной длины, поэтому даже если ограничения были бы немного больше, риска переполнения не возникло бы. В данной задаче максимальный факториал равен 20!, который также без проблем помещается в стандартные целые типы многих языков.

Worked Examples

Example 1

Вход:

2 1

Step	n	k	n!	k!	(n-k)!	Answer
Read input	2	1	-	-	-	-
Compute factorials	2	1	2	1	1	-
Apply formula	2	1	2	1	1	2

Здесь существует два возможных набора, каждый содержит один из двух скинов.

Example 2

Вход:

4 2

Step	n	k	n!	k!	(n-k)!	Answer
Read input	4	2	-	-	-	-
Compute factorials	4	2	24	2	2	-
Apply formula	4	2	24	2	2	6

Этот пример показывает классический случай. Из четырех различных скинов можно составить шесть различных пар.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Вычисляются три факториала длиной не более `n`.
Space	O(1)	Используется только несколько переменных.

Даже при максимальном значении n = 20 алгоритм выполняет считанные десятки операций, что значительно меньше любых разумных ограничений времени и памяти.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    import sys
    input = sys.stdin.readline

    def fact(x):
        res = 1
        for i in range(2, x + 1):
            res *= i
        return res

    n, k = map(int, input().split())
    print(fact(n) // (fact(k) * fact(n - k)))

def run(inp: str) -> str:
    backup_stdin = sys.stdin
    backup_stdout = sys.stdout
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()

    out = sys.stdout.getvalue()

    sys.stdin = backup_stdin
    sys.stdout = backup_stdout
    return out

# provided sample
assert run("2 1\n") == "2\n", "sample 1"

# custom cases
assert run("1 1\n") == "1\n", "minimum input"
assert run("3 3\n") == "1\n", "choose all elements"
assert run("5 2\n") == "10\n", "standard combination"
assert run("20 10\n") == "184756\n", "maximum boundary"

Test input	Expected output	What it validates
`1 1`	`1`	Minimum allowed values
`3 3`	`1`	Choosing every element
`5 2`	`10`	General combination computation
`20 10`	`184756`	Largest input values

Edge Cases

Когда k = 1, алгоритм вычисляет

2 1

Факториалы равны 2! = 2, 1! = 1 и 1! = 1. Формула возвращает 2 / (1 × 1) = 2. Это соответствует двум возможным одноэлементным наборам.

Когда k = n, например

3 3

получаем 3! / (3! × 0!) = 6 / (6 × 1) = 1. Факториал нуля корректно равен единице, поскольку цикл в функции сразу завершается и начальное значение 1 остается неизменным.

Для максимального случая

20 10

функция вычисляет три факториала и получает ответ 184756. Все вычисления выполняются в целых числах, поэтому ошибки округления отсутствуют, а Python без проблем хранит все промежуточные значения.