ОЛИМПИАДА ИНФОРМАТИКЕ ПОМОГИТЕ ПОЖАЛУСТА СРОЧНО
Сдать решение задачи A-Подвох
Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M
Задача A: Подвох
На бумаге нарисована окружность. На окружности отмечено
точек. Проведены всевозможные хорды, соединяющие данные точки. Оказалось, что никакие три хорды не проходят через одну точку.
Саша взял ножницы и вырезал из бумаги круг, а потом разрезал по всем хордам. На сколько частей развалился круг?
Формат входных данных
В первой строке дано целое число
(
) — количество точек.
Формат результата
Выведите единственное целое число — ответ на задачу.
Примеры
def number_of_parts(n):
if n < 2:
return 1
if n == 2:
return 2
if n == 3:
return 4
# P(n) = 1 + C(n, 2) + C(n, 4)
# C(n, 2) = n! / (2! * (n-2)!) = n * (n - 1) / 2
comb_2 = n * (n - 1) // 2
# C(n, 4) = n! / (4! * (n-4)!) = n * (n-1) * (n-2) * (n-3) / (4 * 3 * 2 * 1)
comb_4 = 0
if n >= 4:
comb_4 = n * (n - 1) * (n - 2) * (n - 3) // 24
return 1 + comb_2 + comb_4
# Чтение входных данных
n = int(input())
print(number_of_parts(n))
Удачи