Ограничение времени 2 секунды
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Несколько игроков играют в следующую игру: изначально дан правильный многоугольник с
N
вершинами, в котором не проведено ни одной диагонали. Ход игрока заключается в том, что он соединяет две не соседние вершины многоугольника диагональю так, чтобы она не пересекала уже проведённые диагонали в какой-либо точке, не являющейся вершиной многоугольника (в частности, это обозначает, что совпадающие диагонали проводить нельзя).
Игра заканчивается, когда ход сделать невозможно. Правила подсчёта очков в этой игре слишком сложны, и здесь мы их приводить не будем. Выведите наименьшее суммарное количество ходов, сделанных игроками.
Ограничение времени 2 секунды
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Несколько игроков играют в следующую игру: изначально дан правильный многоугольник с
N
вершинами, в котором не проведено ни одной диагонали. Ход игрока заключается в том, что он соединяет две не соседние вершины многоугольника диагональю так, чтобы она не пересекала уже проведённые диагонали в какой-либо точке, не являющейся вершиной многоугольника (в частности, это обозначает, что совпадающие диагонали проводить нельзя).
Игра заканчивается, когда ход сделать невозможно. Правила подсчёта очков в этой игре слишком сложны, и здесь мы их приводить не будем. Выведите наименьшее суммарное количество ходов, сделанных игроками.
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Несколько игроков играют в следующую игру: изначально дан правильный многоугольник с
N
вершинами, в котором не проведено ни одной диагонали. Ход игрока заключается в том, что он соединяет две не соседние вершины многоугольника диагональю так, чтобы она не пересекала уже проведённые диагонали в какой-либо точке, не являющейся вершиной многоугольника (в частности, это обозначает, что совпадающие диагонали проводить нельзя).
Игра заканчивается, когда ход сделать невозможно. Правила подсчёта очков в этой игре слишком сложны, и здесь мы их приводить не будем. Выведите наименьшее суммарное количество ходов, сделанных игроками.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Давайте подойдем к этой задаче с точки зрения жадного алгоритма. Мы можем заметить, что каждая диагональ, проведенная в многоугольнике, разбивает его на два многоугольника с меньшим числом вершин. Поэтому каждый ход добавляет одну диагональ и уменьшает количество вершин на единицу.
Если у нас есть многоугольник с количеством вершин от 3 до 4, мы можем провести все возможные диагонали, и игра закончится.Если у нас есть многоугольник с количеством вершин от 5 до 7, мы можем провести диагональ, разбивая его на два многоугольника с 3 и N−3N-3N−3 вершинами.И так далее.Исходя из этого, мы можем сделать следующее рассуждение:
Итак, чтобы получить наименьшее количество суммарных ходов, нам нужно разбивать многоугольник на два подмногоугольника с наименьшим числом вершин. Поэтому ответом на задачу будет N-2, где N - количество вершин в исходном многоугольнике.
Пример:
Входные данные:
5
Выходные данные:
3
Пояснение:
В начале у нас есть пятиугольник. Проводим диагональ, разбиваем на треугольник и четырехугольник. Проводим еще 2 диагонали, до полного разделения на треугольники. Всего 3 хода.