Boxes2023#192

Boxes2023 (Розбір)

Коробки не можна ані повертати на бік, ані вкладати одна в одну, а їхні дна — квадрати зі сторонами , , . Отже, треба розмістити три квадрати без перекриттів у прямокутнику найменшої площі.

Для трьох квадратів існує лише два принципово різні розкладки.

Перша: усі три стоять в один ряд. Тоді ширина дорівнює A + B + C, а висота — \max(A, B, C), і площа становить

(A + B + C) \cdot \max(A, B, C).

Друга: один квадрат стоїть окремо, а два інші — поруч один з одним під (або над) ним. Якщо окремо стоїть квадрат зі стороною , а і стоять поруч, то ширина дорівнює \max(A,\; B + C), а висота — A + \max(B, C).

У другому випадку важливо, який саме квадрат стоїть окремо, тому переберемо всі три варіанти (або, що те саме, всі 3! = 6 перестановок). Відповідь — мінімум площі серед усіх розглянутих розкладок, включно з першою.

Сторони сягають 10^9, тому площа доходить до 10^{18} — обов'язково рахуйте у 64-бітному типі, інакше отримаєте переповнення.