KM31. Бумажные многоугольники

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов [latex]r[/latex] нужно сделать, чтобы среди полученных частей оказалось [latex]n[/latex] [latex]k[/latex] -угольников?

Входные данные:

Количество многоугольников [latex]n[/latex].
Количество углов многоугольника [latex]k[/latex].

Выходные данные:

Количество разрезов [latex]r[/latex].

Пример получения двух шестиугольников за 5 разрезов

Пример получения двух шестиугольников за 5 разрезов

Тесты

 Входные данные  Выходные данные
 №  [latex]n[/latex]  [latex]k[/latex]  [latex]r[/latex]
 1  100  20  1699
 2  14  3  13
 3  1  3  1
 4  40  360  14279
 5  2  6  5

Код программы

Решение

При каждом разрезе количество кусков бумаги [latex]n[/latex] увеличивается на [latex]1[/latex]. Общее количество вершин [latex]k[/latex] будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на [latex]4[/latex]. При разрезе через две вершины общее количество вершин увеличивается на [latex]2[/latex], а при разрезе через сторону и вершину — на [latex]3[/latex].

При [latex]k>3[/latex] сначала разделим лист на [latex]n[/latex] четырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться [latex]n-1[/latex] разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в [latex]k[/latex] — угольник, на что понадобиться [latex]k-4[/latex] разрезов.Выходит, что на получение [latex]n[/latex] [latex]k[/latex]- угольников нужно сделать не меньше [latex]n(k-4)+n-1[/latex] разрезов, значит [latex]r=n(k-3)-1[/latex].

Если же [latex]k=3[/latex], то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на [latex]1[/latex] пока не получим [latex]n[/latex]. В таком случае [latex]r= n-1 [/latex]. Исключение: если [latex]n=1[/latex], то [latex]r=1.[/latex]

Ссылки

6 thoughts on “KM31. Бумажные многоугольники

  1. — Если я правильно понял Ваш рисунок, то вы показываете как за 5 (зелёных) разрезов получить два шестиугольника? Тогда добавьте такой тест и сделайте соответствующую подпись к рисунку. И уберите в коде красную линию, которую Выпотом закрашиваете чёрным.
    — Сделайте правильные отступы в коде.
    — Дайте ссылку на программу на ideone.com.
    — Добавьте слова «разрез», «квадрат» в ключевые.
    — Что здесь делают условные операторы? Задача ведь на линейные алгоритмы.

    • Исправил. На счёт последнего замечания: дело в том, что изначально в задаче рассматривают только 20- угольники, а для треугольников формула немного отличается от остальных многоугольников. Возможно, мне стоит изменить категорию на «Программы с ветвлением» или не рассматривать треугольники вовсе?

      • В Вашем случае нужен не условный оператор, а тернарная операция т.к. во всех трёх случаях происходит присваивание r некоторого значения. Только все хорошенько проверьте после переделки.

          • — Нет, Тимур, так не стоит делать. Давайте так, вместо 7-й и 8-й строк напишите одну r=...
            — Вы пишите «Ссылки». Но ссылка одна. И та странно озаглавлена. Важно ведь не то, что она находится на ideone.com или, например, на cpp.sh, а то, что она позволяет выполнить Ваш код.

Comments are closed.