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

Напишите программу MATCHES, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.

Единственная строка входного файла MATCHES.DAT содержит одно целое число N (1≤N≤10⁹).

Единственная строка выходного файла MATCHES.SOL должна содержать одно целое число - минимальное количество спичек требуемых для составления заданного количества квадратов.

   Решение

Тема:    [ Соображения непрерывности ]

Сложность: 3 Классы: 7,8

Прислать комментарий

Условие

Шеренга новобранцев стояла лицом к сержанту. По команде "налево" некоторые повернулись налево, некоторые – направо, а остальные – кругом.
Всегда ли сержант сможет встать в строй так, чтобы с обеих сторон от него оказалось поровну новобранцев, стоящих к нему лицом?

Подсказка

Двигайте сержанта вдоль строя. Число стоящих лицом к сержанту при этом меняется не более чем на 1.

Решение

  Для каждого положения сержанта в строю вычислим разность d между количеством человек, стоящих слева от сержанта к нему лицом, и количеством человек, стоящих справа от сержанта к нему лицом. Посмотрим, как это число меняется при сдвиге сержанта на одно место вправо. Если он "проходит" новобранца, стоявшего к нему спиной, то d увеличивается на 1. Если сержант "проходит" новобранца, стоявшего к нему лицом, то d уменьшается на 1. Иначе d не меняется.
  Ясно также, что, когда сержант стоит крайним слева, d неположительно, а когда он стоит крайним справа, d неотрицательно. Поскольку на каждом шаге d меняется не более чем на 1, где-то "по дороге" оно примет значение 0. В этом положении с обеих сторон от сержанта лицом к нему находится поровну новобранцев.

Ответ

Всегда.

Источники и прецеденты использования