e-olymp 8. Спички

Задача

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [latex]n[/latex] квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

Напишите программу, которая по количеству квадратов [latex]n[/latex], которое необходимо составить, находит минимальное необходимое для этого количество спичек.

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

Одно целое число [latex]n[/latex] [latex](1 ≤ n ≤ 10^9)[/latex].

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

Вывести минимальное количество спичек, требуемых для составления [latex]n[/latex] квадратов.

Тесты

Входные данные Выходные данные
[latex]1[/latex] [latex]4[/latex]
[latex]2[/latex] [latex]7[/latex]
[latex]4[/latex] [latex]12[/latex]
[latex]7[/latex] [latex]20[/latex]
[latex]150[/latex] [latex]325[/latex]
[latex]10000[/latex] [latex]20200[/latex]
Один квадрат можно составить из [latex]4[/latex] спичек. Два квадрата — из [latex]7[/latex] спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, “близкий” к квадрату.
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 2, хотя количество квадратов одинаковое:

  1. matches_1
  2. matches_2

Зададим размеры прямоугольника. Пусть [latex]w = \sqrt n[/latex] — его ширина. Округлим значение [latex]w[/latex] к наибольшему целому числу, не превышающему данное. Тогда его длина будет [latex]l = \displaystyle\frac {n} {w}[/latex]. Если округлить значение [latex]l[/latex] к наибольшему целому числу, не превышающему данное, то мы сможем построить лишь те квадраты, которые входят в наш прямоугольник. Округляя же значение [latex]l[/latex] к наименьшему целому числу, которое не меньше данного, мы сможем достроить квадраты, не поместившиеся в наш прямоугольник.
Если отложить вниз количество спичек, равное [latex]w[/latex], и вправо — [latex]l[/latex], получается следующий рисунок (разумеется, количество отложенных спичек меняется в зависимости от [latex]n[/latex]):
matches_3
Очевидно, что достроить треубемые квадраты можно, положив «уголки» из двух спичек, начиная с левого верхнего угла и двигаясь сверху вниз и слева направо.
«Уголок»:
matches_4
Отсюда и получается формула: [latex]k = 2 \cdot n + l + w[/latex], где [latex]k[/latex] — количество спичек, требуемое в задаче.

Ссылки

Условие задачи на e-olymp
Код решения

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

Задача

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

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

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

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

Количество разрезов r.

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

Тесты

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

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

 

Решение

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

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

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

Ссылка на Ideone

http://ideone.com/X0D8jF