Мастер-класс Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Антон…
- User
Мастер-класс
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Антон Алексеевич, преподаватель математики в старшей школе, решил продемонстрировать практическое применение математических расчётов и провести мастер-класс по очистке квадратной маркерной доски длины в квадратной губкой
длины а.
Антон Алексеевич использует свой фирменный метод, затирая каждый сантиметр доски без лишних движений. Он начинает с верхнего левого угла доски, двигаясь слева направо, затем вниз, влево, вверх, повторяя этот процесс, пока вся доска не будет очищена, но не проходя губкой по тем местам, которые уже очищены (см. рисунок ниже). Губка не вращается во время стирания с доски. Гарантируется, что длина стороны губки делит длину стороны доски без остатка.
Определите длину ломаной линии, которую описывает верхний левый угол квадратной губки при затирании квадратной доски.
Формат входных данных
Первая строка содержит целое число п (1 ≤ n ≤109) длину стороны доски. Вторая строка содержит целое число а (1 < а ≤ 10º, a ≤ n) — длину стороны губки. и делится на а без остатка.
Формат выходных данных
В единственной строке выведите число длину ломаной, которую пройдёт левый верхний угол губки.
Обратите внимание, что ответ в этой задаче может превышать возможное значение
32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и С#).
Система оценки
Решения, правильно работающие при п, а ≤ 10^3, будут оцениваться в 40 баллов.|
Пример: ввод: 6 2 вывод: 16
- Assistant
Чтобы решить эту задачу, нужно определить длину ломаной линии, которую проходит верхний левый угол губки при очистке квадратной доски. Рассмотрим пошагово решение:
Шаг 1: Разбиение доски на сетку
Поскольку длина стороны губки
aполностью делит длину стороны доскиn, мы можем разбить доску на сетку размеромm × m, гдеm = n / a.Шаг 2: Определение пути губки
Губка начинает движение с верхнего левого угла доски и очищает её, перемещаясь по сетке спиральным образом или "змейкой". При этом губка не проходит по уже очищенным участкам.
Шаг 3: Вычисление длины пути
Каждый раз, когда губка перемещается на один сегмент сетки, она проходит расстояние
a. Для сети размеромm × mобщее количество сегментов, которые пройдёт губка, равноm² - 1(так как стартовая позиция не добавляет к длине пути).Таким образом, общая длина пути равна: [ \text{Длина пути} = (m^2 - 1) \times a ]
Пример:
Для входных данных:
6 2m = 6 / 2 = 3- Длина пути:
(3² - 1) × 2 = 8 × 2 = 16
Реализация на Python:
Поскольку значения могут быть достаточно большими (до (10^{27})), удобно использовать язык Python, который поддерживает произвольную точность целых чисел.
n = int(input()) a = int(input()) m = n // a total_length = (m * m - 1) * a print(total_length)Объяснение кода:
- Читаем значения
nиa. - Вычисляем количество сегментов по одной стороне сетки
m. - Вычисляем общую длину пути по формуле ((m^2 - 1) \times a).
- Выводим результат.
Проверка:
Для приведенного примера:
- Ввод:
6 2 - Вывод:
16
Таким образом, решение корректно вычисляет длину пути губки на доске.