Кольорова матриця#201

Кольорова матриця (Розбір)

Відповідь залежить лише від парності .

Непарне : двох кольорів достатньо. Пофарбуємо клітинку у колір (i + j) \bmod 2. Манхеттенська відстань між клітинками дорівнює |\Delta i| + |\Delta j|, а величина (i+j) змінюється на \Delta i + \Delta j, що має ту саму парність. Тому якщо відстань дорівнює непарному , то суми i+j у двох клітинок мають різну парність, отже кольори різні.

Менше двох кольорів не буває: за умовою k < \min(n, m), тому пара клітинок на відстані рівно у полі точно існує.

Парне : потрібно рівно чотири. Спершу покажемо, що трьох замало. Розглянемо чотири клітинки

(0,0),\quad \left(\tfrac{k}{2}, \tfrac{k}{2}\right),\quad (0, k),\quad \left(-\tfrac{k}{2}, \tfrac{k}{2}\right)

(вони цілочисельні саме тому, що парне). Неважко перевірити, що будь-які дві з них перебувають на відстані рівно , тому всі чотири мусять мати різні кольори.

Тепер конструкція на чотири кольори. Перейдемо до повернутих координат

u = i + j, \qquad v = i - j.

Тоді \max(|\Delta u|, |\Delta v|) = |\Delta i| + |\Delta j|, тобто манхеттенська відстань перетворюється на відстань Чебишова. Отже, для клітинок на відстані виконується |\Delta u| = k або |\Delta v| = k.

Пофарбуємо клітинку парою бітів

\left(\left\lfloor \frac{u}{k} \right\rfloor \bmod 2,\;\; \left\lfloor \frac{v}{k} \right\rfloor \bmod 2\right),

що дає чотири кольори. Якщо дві клітинки різняться в координаті рівно на , то їхні значення різняться рівно на одиницю, тобто перший біт відрізняється; аналогічно для . Отже, кольори різні.

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

Складність — , тобто просто виведення поля.