Подарунок для Антона (Розбір)

10pt

Блок 0

Якщо є хоча б одна «4», то всі поруч з нею теж «4», поруч з цією «4» теж всі «4», і так далі. А таблиця скінченна, отже, такого не може бути.

Якщо є хоча б одна «3», то розглянемо найвищу з усіх «3». Тоді у всіх напрямках, окрім верхнього, вона межує з іншими «3». Розглянемо ту «3», що справа від початкової. В неї аналогічно зліва, знизу та справа інші «3». І так далі, можемо розширюватись вправо до нескінченності, а таблиця скінченна, суперечність.

Двійки утворюють циклічні структури. Одинички розташовані доміношками. Нулі є ізольованими від інших нулів. Це яскраво видно з прикладу із умови.

Описані вище роздуми не є обов'язковими, але подібний аналіз завдання дуже допомігає розв'язанню.

Блок 1 (n = 1)

Нескладно помітити, що, чергуючи доміношки «1-1» та ізольовані «0», можна отримати ланцюг довільної довжини.

Блок 2 (n = 2)

Якщо продублювати рішення на Блок 1 і збільшити всі числа на 1, то воно буде працювати на цей блок.

Блок 2 (n = 3)

Якщо обрамлення зробити з «2», то лишиться стрічка 1 \times (m-2), для якої можна викликати рішення для Блоку 1.

Блок 3

Візмемо приклад з умови. Відріжемо найлівіший і найправіший стовпець. Кути поміняємо з «1» на «0».

Блоки 5-11

Якщо поставити поруч з квадратиком з «2» дві доміношки з «1» та ізольований «0», то отримаємо паттерн 3 \times 3, який можна повторювати нескінченно.

Більше того, якщо розглянути конкретний рядок, то помітимо, що в нас завжди така ситуація, як в блоці 1: дві однакові цифри, одна інша, дві однакові, одна інша... Це значить, що так само як і в Блоці 1, ми можемо обрати відрізок з $m$ стовпців, щоб на границях не було проблем. Аналогічно можна обрати відрізок з $n$ рядків, щоб на границях не було проблем. Відповідь — таблиця, що утворена перетином цих $n$ рядків та $m$ стовпців.

Блок 8