Мастер‑класс Антон Алексеевич, преподаватель математики в старшей школе, решил продемонстрировать практическое применение математических расчётов и провести мастер‑класс по…
Мастер‑класс Антон Алексеевич, преподаватель математики в старшей школе, решил продемонстрировать практическое применение математических расчётов и провести мастер‑класс по очистке квадратной маркерной доски длины n квадратной губкой длины a. Антон Алексеевич использует свой фирменный метод, затирая каждый сантиметр доски без лишних движений. Он начинает с верхнего левого угла доски, двигаясь слева направо, затем вниз, влево, вверх, повторяя этот процесс, пока вся доска не будет очищена, но не проходя губкой по тем местам, которые уже очищены (см. рисунок ниже). Губка не вращается во время стирания с доски. Гарантируется, что длина стороны губки делит длину стороны доски без остатка. Определите длину ломаной линии, которую описывает верхний левый угол квадратной губки при затирании квадратной доски. Формат входных данных Первая строка содержит целое число n (1≤n≤109) длину стороны доски. Вторая строка содержит целое число a (1≤a≤109, a≤n) длину стороны губки. nn делится на a без остатка. Формат выходных данных В единственной строке выведите число длину ломаной, которую пройдёт левый верхний угол губки. Обратите внимание, что ответ в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Система оценки Решения, правильно работающие при n, a≤103, будут оцениваться в 40 баллов. Замечание Проиллюстрируем пример к условию. Жёлтым на схеме обозначена губка, голубым очищенная область, красным маршрут левого верхнего угла губки.
Для решения данной задачи начнем с понимания, как располагается губка на доске и какой маршрут описывает её левый верхний угол.
При нанесении губки на квадратную доску длиной \( n \) с губкой длиной \( a \) (где \( n \) делится на \( a \) без остатка), мы можем предположить, что кубик будет двигаться по рядам и колонкам, оставляя за собой очищенные области.
Определение количества движений:
- Количество полных сегментов губки по одной стороне доски можно вычислить как \( k = \frac{n}{a} \). Это означает, что на доске у нас будет \( k \) положений губки по горизонтали и \( k \) по вертикали.
Схема движения:
- Губка начинает с верхнего левого угла доски и движется слева направо. Когда она достигает правого края, она перемещается вниз и затем движется справа налево и так далее, описывая "змейку".
- Таким образом, сначала губка проходит \( a \) см по горизонтали, затем перемещается вниз на \( a \) см, снова проходит \( a \) см по горизонтали, и так далее.
Длина ломаной линии:
- На первом уровне (первый проход) губка пройдет \( a \) см по горизонтали, затем спустится вниз на \( a \) см, второй проход снова \( a \) см по горизонтали, и так продолжается.
- Губка завершит последнюю проход с перемещением вниз, но уже не будет движения в сторону, так как заканчивается на нижней границе.
Таким образом, длина пути, который проходит левый верхний угол губки, будет равной:
- Горизонтальные перемещения: \( (k - 1) \) раз по \( a \) см в каждую сторону (всего \( 2(k-1)a \)).
- Вертикальные перемещения: \( k \) раз по \( a \) см.
Итоговая формула, получаемая из описанного выше, будет: \[ \text{Длина ломаной линии} = 2 \times (k - 1) \times a + (k \times a) = (2k - 1) \times a \]
Подставляем \( k = \frac{n}{a} \): \[ \text{Длина ломаной линии} = (2 \cdot \frac{n}{a} - 1) \cdot a = 2n - a \]
Таким образом, ответ на задачу:
\[ \text{Длина ломаной линии} = 2n - a \]
Это и будет искомый результат, который необходимо вывести.
