e-olymp 8. Спички

Latest posts by Алиса Ворохта (see all)

Задача

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [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)

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
Код решения

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

Задача

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

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

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

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

Количество разрезов [latex]r[/latex].

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

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

Тесты

 Входные данные  Выходные данные
 №  [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

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

Решение

При каждом разрезе количество кусков бумаги [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]

Ссылки

e-olymp 2061. Юные программисты

Андрей Яроцкий
Андрей Яроцкий

Latest posts by Андрей Яроцкий (see all)

Задача

Известно, что в школе не менее чем [latex]k_1[/latex]  учеников, но не более чем [latex]k_2[/latex] учеников. Также известно, что каждый мальчик дружит с [latex]n[/latex] девочками, а каждая девочка с [latex]m[/latex] мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Тесты:

Ввод Вывод
1 20 30 4 5 27 15 12
2 40 50 5 4 45 20 25

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

Решение:

Увеличиваем количество девочек на 1 пока количество мальчиков по формуле [latex]b = g \cdot m / n[/latex] не станет целочисельным значением и сумма мальчиков и девочек будет больше или равна минимальному возможному количеству учеников [latex]k_1[/latex].

  • Условие задачи можно найти на сайте e-olymp.
  • Ссылка на решение задачи на ideone.com здесь.
  • Ссылка на полностью решенную задачу здесь.

Mif 16

Условие :

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

Решение :

Команда ветвления (конструкция «if {} else {}» или тернарный оператор «?» ) разделяет код программы с какого-то момента ровно на 2 независимых алгоритма (даже при отсутствии блока «else {}», так как программа продолжает выполняться в зависимости от того, сработал блок «if {}», или нет). Таким образом, если понимать под «вариантов поведения» изолированный блок кода, выполняемый при совпадении набора условий, чтобы разбить программу на [latex]n[/latex] таких независимых вариантов, нужно использовать ровно [latex]n — 1[/latex] условную операцию.

Тесты : 

Входные данные 12 7 1 0
Выходные данные 11 6 0 Ошибка ввода

Код :

Ссылка на рабочий код:

Ideone.com