Освітлення#13007

Освітлення (Editorial)

Лампа освітлює цілий рядок або цілий стовпець, і кожен рядок має дві лампи (ліворуч і праворуч), кожен стовпець — теж дві (згори та знизу). Тому рівень освітленості клітинки дорівнює

a_{i,j} = R_i + C_j,

де R_i \in \{0,1,2\} — кількість увімкнених ламп рядка , а C_j \in \{0,1,2\} — стовпця .

Досить перебрати R_1 \in \{0,1,2\}. Кожен вибір одразу задає всі стовпці: C_j = a_{1,j} - R_1. Стовпець задає всі рядки: R_i = a_{i,1} - C_1. Лишається перевірити, що всі значення лежать у \{0,1,2\} і що рівність R_i + C_j = a_{i,j} виконується для всієї матриці. За умовою розв'язок існує, тож хоча б один із трьох варіантів пройде.

Нарешті кількість перетворюється на конкретні лампи: R_i = 2 — обидві увімкнені, R_i = 1 — одна, R_i = 0 — жодної; так само для стовпців. Відповідь не єдина, і будь-яка з них приймається.

Складність: .

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.