G. Бабочки и Ураганы

Codeforces
IDCF10136G
Time2000ms
Memory256MB
Difficulty
English · Original
Formal · Original
Фронтмен известной рок-группы Мэд построил в своем новом особняке оранжерею, которая представляет собой клеточное поле N × M. В оранжерее Мэд хочет посадить дронов двух моделей: «Бабочка» и «Ураган», при этом он хочет, чтобы дроны заняли все пространство оранжереи. Каждый дрон имеет четыре ноги, которые при посадке занимают по одной клетке так, что эти клетки ограничивают квадрат со сторонами, параллельными границам оранжереи, а сам дрон занимает весь этот квадрат. При этом ноги дрона обязательно должны занимать разные клетки и могут быть расставлены как угодно широко. Чтобы рассадка не выглядела слишком хаотично, Мэд хочет, чтобы дроны занимали квадраты одинаковых размеров, однако, чтобы внести разнообразие, никакие два дрона одной модели не должны касаться друг друга стороной, но могут касаться углами. Необходимо помочь Мэду посадить как можно больше дронов. В единственной строке заданы размеры оранжереи в особняке Мэда N и M (1 ≤ N, M ≤ 100). Если невозможно посадить дронов по описанным правилам, выведите в единственной строке _NO_. Если решение существует, в первой строке выведите _YES_, а в N последующих строках по M символов выведите искомую расстановку дронов. Каждая клетка должна определять модель дрона, который ее занимает. Дрон модели «Бабочка» обозначается латинской буквой _B_, а дрон модели «Ураган» — латинской буквой _X_. Рассадка должна соответствовать следующим условиям: ## Входные Данные В единственной строке заданы размеры оранжереи в особняке Мэда N и M (1 ≤ N, M ≤ 100). ## Выходные Данные Если невозможно посадить дронов по описанным правилам, выведите в единственной строке _NO_.Если решение существует, в первой строке выведите _YES_, а в N последующих строках по M символов выведите искомую расстановку дронов. Каждая клетка должна определять модель дрона, который ее занимает. Дрон модели «Бабочка» обозначается латинской буквой _B_, а дрон модели «Ураган» — латинской буквой _X_.Рассадка должна соответствовать следующим условиям: все дроны должны занимать квадраты одного размера со стороной больше единицы; дроны одной модели могут соприкасаться только углами; каждая клетка оранжереи должна быть занята каким-либо дроном; в левом верхнем углу оранжереи должен сидеть дрон модели «Бабочка». ## Примеры Входные данные8 4Выходные данныеYESBBXXBBXXXXBBXXBBBBXXBBXXXXBBXXBBВходные данные6 9Выходные данныеYESBBBXXXBBBBBBXXXBBBBBBXXXBBBXXXBBBXXXXXXBBBXXXXXXBBBXXXВходные данные5 5Выходные данныеYESBBBBBBBBBBBBBBBBBBBBBBBBBВходные данные1 3Выходные данныеNO [samples]
**Definitions** Let $ N, M \in \mathbb{Z} $ be the dimensions of the grid, with $ 1 \leq N, M \leq 100 $. Let $ k \in \mathbb{Z}^+ $ be the side length of the square occupied by each drone (i.e., each drone occupies a $ k \times k $ block). Let the grid be partitioned into non-overlapping $ k \times k $ blocks, each occupied by exactly one drone. Let two drone models be denoted: $ B $ (Butterfly) and $ X $ (Hurricane). **Constraints** 1. Each drone occupies a contiguous $ k \times k $ square of cells. 2. The entire $ N \times M $ grid must be partitioned into such $ k \times k $ squares (i.e., $ k \mid N $ and $ k \mid M $). 3. No two drones of the same model may share an edge (4-directional adjacency); diagonal (corner) adjacency is allowed. 4. Each cell is occupied by exactly one drone. 5. The number of drones is maximized (i.e., $ k $ is minimized subject to constraints). **Objective** Find the smallest $ k \in \mathbb{Z}^+ $ such that $ k \mid N $, $ k \mid M $, and the $ \frac{N}{k} \times \frac{M}{k} $ grid of drone positions admits a 2-coloring (with colors $ B $ and $ X $) such that no two adjacent (edge-sharing) cells have the same color. If such $ k $ exists, output a valid coloring; otherwise, output "NO".
API Response (JSON)
{
  "problem": {
    "name": "G. Бабочки и Ураганы",
    "description": {
      "content": "Фронтмен известной рок-группы Мэд построил в своем новом особняке оранжерею, которая представляет собой клеточное поле N × M. В оранжерее Мэд хочет посадить дронов двух моделей: «Бабочка» и «Ураган», ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10136G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Фронтмен известной рок-группы Мэд построил в своем новом особняке оранжерею, которая представляет собой клеточное поле N × M. В оранжерее Мэд хочет посадить дронов двух моделей: «Бабочка» и «Ураган», ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 1 \\leq N, M \\leq 100 $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the side length of the square occupied by each drone (i.e., ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments