РАЗБОР | Задача 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.

💭 Если решали иначе, делитесь вариантом в комментариях — обсудим!