Ограничение времени2 секунды Ограничение памяти512Mb Вводстандартный ввод или input.txt Выводстандартный…
Ограничение времени2 секунды Ограничение памяти512Mb Вводстандартный ввод или input.txt Выводстандартный вывод или output.txt Несколько игроков играют в следующую игру: изначально дан правильный многоугольник с N вершинами, в котором не проведено ни одной диагонали. Ход игрока заключается в том, что он соединяет две не соседние вершины многоугольника диагональю так, чтобы она не пересекала уже проведённые диагонали в какой-либо точке, не являющейся вершиной многоугольника (в частности, это обозначает, что совпадающие диагонали проводить нельзя). Игра заканчивается, когда ход сделать невозможно. Правила подсчёта очков в этой игре слишком сложны, и здесь мы их приводить не будем. Выведите наименьшее суммарное количество ходов, сделанных игроками. Формат ввода Входные данные содержат одно целое число N — количество вершин многоугольника ( 4 ≤ N ≤ 1 0 0 0 ). Формат вывода Выведите одно число — наименьшее суммарное количество ходов, сделанных игроками. В примере в случае правильного четырёхугольника (то есть квадрата) первый игрок проводит диагональ, после чего игра автоматически заканчивается: оставшаяся диагональ пересекается с уже проведённой. Пример ВводВывод 4 1 Примечания Решением этой задачи должна являться программа на одном из представленных в системе языков программирования, решающая данную задачу. Программа должна считывать данные со стандартного ввода (клавиатуры) и выводить на стандартный вывод (монитор). Никаких дополнительных строк или символов выводить не разрешается.
Ответ:
n = int(input())
m = 2 * n — 1
field = [[0] * m for _ in range(m)]
field[0][0] = 1
for x in range(m):
for y in range(m):
if m >= y — x + n > 0:
if x > 0:
field[y][x] += field[y][x — 1]
if y > 0:
field[y][x] += field[y — 1][x]
if x > 0 and y > 0:
field[y][x] += field[y — 1][x — 1]
print(field[m — 1][m — 1])