Question

Ограничение времени 2 секунды Ограничение памяти 512Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Несколько игроков играют в следующую игру: изначально дан правильный многоугольник с N вершинами, в котором не проведено ни одной диагонали. Ход игрока заключается в том, что он соединяет две не соседние вершины многоугольника диагональю так, чтобы она не пересекала уже проведённые диагонали в какой-либо точке, не являющейся вершиной многоугольника (в частности, это обозначает, что совпадающие диагонали проводить нельзя). Игра заканчивается, когда ход сделать невозможно. Правила подсчёта очков в этой игре слишком сложны, и здесь мы их приводить не будем. Выведите наименьшее суммарное количество ходов, сделанных игроками. Формат ввода Входные данные содержат одно целое число N — количество вершин многоугольника ( 4 ≤ N ≤ 1 0 0 0 ). Формат вывода Выведите одно число — наименьшее суммарное количество ходов, сделанных игроками. В примере в случае правильного четырёхугольника (то есть квадрата) первый игрок проводит диагональ, после чего игра автоматически заканчивается: оставшаяся диагональ пересекается с уже проведённой. Пример Ввод Вывод 4 1 Примечания Решением этой задачи должна являться программа на одном из представленных в системе языков программирования, решающая данную задачу. Программа должна считывать данные со стандартного ввода (клавиатуры) и выводить на стандартный вывод (монитор). Никаких дополнительных строк или символов выводить не разрешается.

Answer 1

Ответ:

N = int(input())

print(N-3)

Объяснение:

Answer 2

Данная задача связана с графами и теорией игр. Она также известна как задача о максимальном количестве непересекающихся диагоналей в выпуклом многоугольнике.

Чтобы решить эту задачу, можно заметить следующую закономерность: каждый игрок проводит одну диагональ, и после этого остается многоугольник с (N-2) вершинами. Таким образом, на каждом шаге количество вершин уменьшается на 2.

Так как игра заканчивается, когда ход сделать невозможно, это происходит тогда, когда количество вершин N станет меньше или равно 3.

Таким образом, чтобы найти наименьшее суммарное количество ходов, мы должны подсчитать, сколько раз можно уменьшить количество вершин на 2 до тех пор, пока N не станет меньше или равно 3.

Пример псевдокода для решения задачи:

mathematicaCopy code
read N
count = 0

while N > 3:
    N = N - 2
    count = count + 1

print count

В случае, если на входе число N равно 4 (как в примере), программа выведет 1, что означает, что игроку потребуется сделать 1 ход, чтобы закончить игру.

Заметим, что это решение работает за O(log(N)) времени, что приемлемо для данного диапазона N (4 ≤ N ≤ 1000).