Задача
Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [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] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); double n = in.nextDouble(); double length = Math.floor(Math.sqrt(n)); double width = Math.ceil(n / length); double k = 2 * n + length + width; System.out.print((int)(k)); } } |
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 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]):
Очевидно, что достроить треубемые квадраты можно, положив «уголки» из двух спичек, начиная с левого верхнего угла и двигаясь сверху вниз и слева направо.
«Уголок»:
Отсюда и получается формула: [latex]k = 2 \cdot n + l + w[/latex], где [latex]k[/latex] — количество спичек, требуемое в задаче.