Ключове спостереження: спосіб розрізання визначається не всіма розмірами, а лише схемою розрізу. Розрізати прямокутник на три прямокутники можна лише двома принципово різними способами.
Схема 1: три паралельні смуги. Розріжемо кімнату двома паралельними прямими. Якщо смуги йдуть уздовж сторони і мають ширини k_1 + k_2 + k_3 = m, то сумарний периметр дорівнює
Він не залежить від того, як саме поділено ! Тому ця схема підходить лише за умови 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. Сумарний периметр дорівнює
Тут периметр уже залежить від , тому просто виражаємо його:
і перевіряємо, що парне, 1 \le k < m та n \ge 2. Симетричний варіант — з переставленими ролями і .
Отже, розв'язок — перебрати ці чотири випадки. Щойно якийсь підійшов, виводимо YES і розміри трьох кімнат; якщо жоден не підійшов — NO.
Зверніть увагу, що периметр завжди парний, тому за непарного відповідь одразу NO.