Задача
Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [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 |
#include <iostream> #include <cmath> using namespace std; int main() { long long n, k; long double length, width; cin >> n; length = floor(sqrt(n)); width = ceil(n/length); k = 2*n + length + width; cout << k << endl; return 0; } |
Решение задачи
Один квадрат можно составить из [latex]4[/latex] спичек. Два квадрата — из [latex]7[/latex] спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, “близкий” к квадрату.
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 2, хотя количество квадратов одинаковое:
Зададим размеры прямоугольника. Пусть [latex]width = \sqrt n[/latex] — его ширина. Округлим значение [latex]width[/latex] к наибольшему целому числу, не превышающему данное. Тогда его длина будет [latex]length = \frac {n} {width}[/latex]. Если округлить значение [latex]length[/latex] к наибольшему целому числу, не превышающему данное, то мы сможем построить лишь те квадраты, которые входят в наш прямоугольник. Округляя же значение [latex]length[/latex] к наименьшему целому числу, которое не меньше данного, мы сможем достроить квадраты, не поместившиеся в наш прямоугольник.
Если отложить вниз количество спичек, равное [latex]width[/latex], и вправо — [latex]length[/latex], получается следующий рисунок (разумеется, количество отложенных спичек меняется в зависимости от [latex]n[/latex]):
Очевидно, что достроить треубемые квадраты можно, положив «уголки» из двух спичек, начиная с левого верхнего угла и двигаясь сверху вниз и слева направо.
«Уголок»:
Отсюда и получается формула: [latex]k = 2 \cdot n + length + width [/latex], где [latex]k[/latex] — количество спичек, требуемое в задаче.
Ссылки
Условие задачи на e-olymp
Код решения
Хорошо. Хотя математики и физики (в отличие от программистов) не любят длинные названия переменных. Обычно математики ограничиваются в формулах одной буквой для переменной.
+10 за DIY SVG. Это ценный опыт.
Спасибо, учту на будущее