Question

Влад М. недавно окончил лицей и наконец-то поступил в лучший университет на свете — СГАУ! Влад — прирождённый лидер, поэтому одногруппники сразу же выбрали его своим старостой. Большая часть занятий в СГАУ проходит по подгруппам, и расписание составлено исходя из того, что каждая группа разделена на две подгруппы. Староста должен составить списки подгрупп и отнести их в деканат. Это означает, что Влад должен записать каждого студента в подгруппу #1 или в подгруппу #2. Разумеется, каждый студент должен быть записан ровно в одну подгруппу. Размеры подгрупп могут быть любыми; допустимо, что в одной из подгрупп может не быть ни одного студента. Некоторые одногруппники уже успели сдружиться, а некоторые, напротив, уже недолюбливают друг друга. Так что на Влада посыпалась куча просьб вида «Я безумно влюблён в XX, поэтому хочу учиться с ней в одной подгруппе», «XY странно смотрит на меня, мне кажется, он сумасшедший, не хочу оказаться в одной подгруппе с ним» и т.д. Конечно, были и пожелания иного рода, например, «Я хочу учиться в подгруппе #1, так как там нет пар в 8 часов утра в понедельник». Но этих просьб и пожеланий было очень, очень много...Предприняв несколько попыток составить списки подгрупп, Влад осознал, что это не так-то просто сделать. Поэтому он решил написать программу, выбирающую такое разбиение на подгруппы, при котором будет удовлетворено наибольшее количество просьб одногруппников.«Достаточно просто перебрать все возможные разбиения на подгруппы и посчитать для каждого разбиения, сколько просьб будет выполнено. Плёвое дело!» — рассуждал Влад. Внезапно его посетила мысль, что количество возможных разбиений может быть настолько большим, что программа не сможет проверить их все не только до конца семестра, но и до конца обучения.Зная, сколько человек учится в группе Влада, помогите ему определить количество возможных разбиений. Если возможных разбиений больше миллиона, скажите ему, что их слишком много. Два разбиения считаются различными, если найдётся хотя бы один студент, который в этих двух разбиениях записан в разные подгруппы.Входные данныеВ первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 109) — количество студентов в группе Влада, включая его самого.Выходные данныеВ первой строке выведите количество возможных разбиений на подгруппы.Если количество возможных разбиений на подгруппы больше 106, выведите вместо количества возможных разбиений TOO HARD (в точности так, как записано).Это Олимпиада, и я незнаю как решать эту задачу...​

Answer 1

правильно это надо посмотреть

Answer 2

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

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

Однако при больших значениях n вычисление чисел Белла может стать вычислительно сложной задачей. В данном случае, если количество разбиений больше 1 миллиона, следует вывести "TOO HARD".

Пример кода на Python:

pythonCopy code
def binomial_coefficient(n, k):
    if k == 0 or k == n:
        return 1
    if k > n - k:
        k = n - k
    result = 1
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result

def bell_number(n):
    bell = [[0] * (n + 1) for _ in range(n + 1)]
    bell[0][0] = 1
    for i in range(1, n + 1):
        bell[i][0] = bell[i - 1][i - 1]
        for j in range(1, i + 1):
            bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]
    return bell[n][0]

n = int(input())
bell = bell_number(n)
if bell > 10**6:
    print("TOO HARD")
else:
    print(bell)

Пример ввода:

Copy code
4

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

Copy code
2

Этот код сначала определяет функции для вычисления биномиальных коэффициентов и чисел Белла. Затем он считывает количество студентов n и вычисляет количество возможных разбиений с помощью чисел Белла. Если это число больше 1 миллиона, выводится "TOO HARD", в противном случае выводится количество разбиений.