e-olymp 2612. Разрезание на квадраты

Задача

Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

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

Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]

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

Требуется вывести количество квадратов.

Тесты

Входные данные Выходные данные
12 4 3
15 3 5
20 20 1
8 12 3

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

 

Решение задачи

Нам было дана высота и ширина полоски бумаги. Есть три варианта:

  • Высота равна ширине
  • Высота больше ширины
  • Высота меньше ширины

В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.

Ссылки

  • Задача на сайте e-olymp
  • Код решения в Ideone

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, хотя количество квадратов одинаковое:

Зададим размеры прямоугольника. Пусть [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
Код решения