Задача
Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов [latex]r[/latex] нужно сделать, чтобы среди полученных частей оказалось [latex]n[/latex] [latex]k[/latex] -угольников?
Входные данные:
Количество многоугольников [latex]n[/latex].
Количество углов многоугольника [latex]k[/latex].
Выходные данные:
Количество разрезов [latex]r[/latex].
Тесты
Входные данные | Выходные данные | ||
№ | [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 |
Код программы
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> using namespace std; int main() { int r, n, k; cin>>n>>k; r=k>3? n*(k-3)-1 : n>1? n-1 : 1; cout<<r; return 0; } |
Решение
При каждом разрезе количество кусков бумаги [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]
Ссылки
- Код программы.
- Условие задачи (страница 47).
— Если я правильно понял Ваш рисунок, то вы показываете как за 5 (зелёных) разрезов получить два шестиугольника? Тогда добавьте такой тест и сделайте соответствующую подпись к рисунку. И уберите в коде красную линию, которую Выпотом закрашиваете чёрным.
— Сделайте правильные отступы в коде.
— Дайте ссылку на программу на ideone.com.
— Добавьте слова «разрез», «квадрат» в ключевые.
— Что здесь делают условные операторы? Задача ведь на линейные алгоритмы.
Исправил. На счёт последнего замечания: дело в том, что изначально в задаче рассматривают только 20- угольники, а для треугольников формула немного отличается от остальных многоугольников. Возможно, мне стоит изменить категорию на «Программы с ветвлением» или не рассматривать треугольники вовсе?
В Вашем случае нужен не условный оператор, а тернарная операция т.к. во всех трёх случаях происходит присваивание r некоторого значения. Только все хорошенько проверьте после переделки.
Понял. Спасибо.
— Нет, Тимур, так не стоит делать. Давайте так, вместо 7-й и 8-й строк напишите одну r=...
— Вы пишите «Ссылки». Но ссылка одна. И та странно озаглавлена. Важно ведь не то, что она находится на ideone.com или, например, на cpp.sh, а то, что она позволяет выполнить Ваш код.
Спасибо. Исправил.