РАЗБОР | Задача 1. Большой квадрат
Муниципальный этап ВсОШ по программированию, 2025/26 учебный год
🖍️
Темы: формулы, математика, перебор, геометрические конструкции
Уровень:
Python Start +
ОлПрактика lvl 1–2
Главное из условия
Даны два прямоугольника: a×b и c×d. Каждый можно повернуть, а затем склеить их сторона к стороне. Длины сторон могут различаться, склеивается только общая часть.
Из получившейся фигуры нужно вырезать квадрат со сторонами, параллельными сторонам прямоугольников. Найдите максимально возможную сторону такого квадрата.
➡️
Шаг 0. Пусть высота будет большей стороной
Прямоугольники можно поворачивать, поэтому сразу упорядочим стороны:
• если a < b — меняем местами, теперь a ≥ b;
• если c < d — меняем местами, теперь c ≥ d.
Теперь у первого прямоугольника высота a и ширина b, у второго высота c и ширина d. Ширины b и d — меньшие стороны.
Ключевая идея
Квадрат может лежать в фигуре одним из трёх способов:
1️⃣ Целиком в первом прямоугольнике. Максимум — b.
2️⃣ Целиком во втором прямоугольнике. Максимум — d.
3️⃣ Пересекает шов склейки. Только в этом случае квадрат может получиться больше, чем в каждом прямоугольнике по отдельности.
В третьем случае квадрат пересекает шов на каждой своей высоте. Значит, он должен целиком помещаться в полосе, где прямоугольники перекрываются.
➡️
Как выгоднее склеивать
Если склеить прямоугольники по коротким сторонам, перекрытие будет не больше min(b, d). Такой квадрат не больше b или d, то есть выигрыша по сравнению со случаями 1 и 2 нет.
Поэтому склеиваем по длинным сторонам: высоты a и c ставим рядом. Тогда квадрат через шов ограничен:
• общей высотой перекрытия: не больше min(a, c);
• общей шириной: не больше b + d.
Его сторона равна min(a, c, b + d), а ответ — максимум из трёх случаев.
➡️
Пример
Прямоугольники 5×2 и 4×3. Ставим их рядом высотами 5 и 4: общая ширина 2 + 3 = 5, перекрытие по высоте 4. Через шов помещается квадрат 4×4, а это больше, чем 2 или 3 по отдельности.
min(5, 4, 5) = 4 → max(2, 3, 4) = 4 ✅
Собираем решение
a, b, c, d = int(input()), int(input()), int(input()), int(input())
if a < b: # делаем a ≥ b
a, b = b, a
if c < d: # делаем c ≥ d
c, d = d, c
val = min(a, c, b + d)
print(max(b, d, val))
↖️
Сложность: O(1) по времени и памяти — только пара сравнений и min/max.
💭 Если решали иначе, делитесь вариантом в комментариях — обсудим!