Козак Вус і цікава задача#133

Козак Вус і цікава задача (Розбір)

Ключове спостереження: спосіб розрізання визначається не всіма розмірами, а лише схемою розрізу. Розрізати прямокутник на три прямокутники можна лише двома принципово різними способами.

Схема 1: три паралельні смуги. Розріжемо кімнату двома паралельними прямими. Якщо смуги йдуть уздовж сторони і мають ширини k_1 + k_2 + k_3 = m, то сумарний периметр дорівнює

2(n + k_1) + 2(n + k_2) + 2(n + k_3) = 6n + 2m.

Він не залежить від того, як саме поділено ! Тому ця схема підходить лише за умови p = 6n + 2m, і потрібно m \ge 3, щоб усі три смуги мали додатну ширину. Симетрично існує варіант p = 6m + 2n при n \ge 3.

Схема 2: один розріз, потім ще один у половинці. Спочатку відріжемо смугу шириною : отримаємо прямокутники n \times (m-k) та n \times k. Другий розріз ділить смугу n \times k на 1 \times k і (n-1) \times k. Сумарний периметр дорівнює

2(n + m - k) + 2(1 + k) + 2(n - 1 + k) = 4n + 2m + 2k.

Тут периметр уже залежить від , тому просто виражаємо його:

k = \frac{p - 4n - 2m}{2},

і перевіряємо, що парне, 1 \le k < m та n \ge 2. Симетричний варіант — з переставленими ролями і .

Отже, розв'язок — перебрати ці чотири випадки. Щойно якийсь підійшов, виводимо YES і розміри трьох кімнат; якщо жоден не підійшов — NO.

Зверніть увагу, що периметр завжди парний, тому за непарного відповідь одразу NO.