Біло-чорне поле#46

Біло-чорне поле (Editorial)

Задача конструктивна: розміри поля ми обираємо самі, тому зручно взяти максимально дозволене поле 50 \times 50 і побудувати відповідь за єдиним шаблоном.

Основа конструкції — поділ поля навпіл: верхня половина (рядки –) повністю біла, нижня (рядки –) повністю чорна. Це дає рівно одну білу й одну чорну компоненту.

Тепер треба додати ще b - 1 чорних і a - 1 білих компонент. Робимо це ізольованими точками: чорна клітинка, поставлена посеред білого поля так, щоб не торкатися інших чорних, утворює окрему чорну компоненту й не розриває білу.

Щоб точки гарантовано не злипалися, ставимо їх лише в клітинки з парними рядком і стовпцем — тоді будь-які дві такі клітинки не сусідні ні по стороні, ні навіть по діагоналі.

Отже:

  • у білій половині розставляємо b-1 чорних точок у клітинки з парними координатами (рядки 0, 2, \ldots, 24);

  • у чорній половині розставляємо a-1 білих точок так само, але починаючи з рядка .

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

Місткості вистачає з великим запасом: у кожній половині доступно 13 \times 25 = 325 позицій, а треба щонайбільше .

Наприкінці виводимо розміри і саме поле. Не забудьте зменшити і на одиницю перед розстановкою — по одній компоненті кожного кольору вже дають самі половини.