A. Domino

Codeforces

IDCF85A

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsimplementation

English · Original

Chinese · Translation

Formal · Original

We all know the problem about the number of ways one can tile a 2 × _n_ field by 1 × 2 dominoes. You probably remember that it goes down to Fibonacci numbers. We will talk about some other problem below, there you also are going to deal with tiling a rectangular field with dominoes. You are given a 4 × _n_ rectangular field, that is the field that contains four lines and _n_ columns. You have to find for it any tiling by 1 × 2 dominoes such that each of the _n_ - 1 potential vertical cuts along the grid lines intersects at least one domino, splitting it in two. No two dominoes in the sought tiling should overlap, each square of the field should be covered by exactly one domino. It is allowed to rotate the dominoes, that is, you can use 2 × 1 as well as 1 × 2 dominoes. Write a program that finds an arbitrary sought tiling. ## Input The input contains one positive integer _n_ (1 ≤ _n_ ≤ 100) — the number of the field's columns. ## Output If there's no solution, print "-1" (without the quotes). Otherwise, print four lines containing _n_ characters each — that's the description of tiling, where each vertical cut intersects at least one domino. You should print the tiling, having painted the field in no more than 26 colors. Each domino should be painted a color. Different dominoes can be painted the same color, but dominoes of the same color should not be side-neighbouring. To indicate colors you should use lowercase Latin letters. Print any of the acceptable ways of tiling. [samples]

我们都知道一个关于用 $1 \times 2$ 多米诺骨牌铺满 $2 \times n$ 网格的方案数的问题，你可能记得它归结为斐波那契数。下面我们讨论另一个问题，你同样需要使用多米诺骨牌铺满一个矩形区域。给定一个 $4 \times n$ 的矩形区域，即包含四行和 $n$ 列的网格。你需要找到一种用 $1 \times 2$ 多米诺骨牌铺满它的方案，使得每一条位于网格线上的潜在垂直切割（共 $n - 1$ 条）都至少穿过一个骨牌，将其分割为两部分。所求铺法中，任意两个骨牌不得重叠，网格中的每个方格必须恰好被一个骨牌覆盖。允许旋转骨牌，即你可以使用 $2 \times 1$ 或 $1 \times 2$ 的骨牌。编写一个程序，找出任意一种满足条件的铺法。输入包含一个正整数 $n$（$1 \leq n \leq 100$）——表示网格的列数。如果无解，输出 "-1"（不含引号）。否则，输出四行，每行包含 $n$ 个字符，描述一种铺法，其中每条垂直切割都至少穿过一个骨牌。你应使用不超过 $26$ 种颜色对铺法进行着色。每个骨牌应被赋予一种颜色，不同骨牌可以使用相同颜色，但相同颜色的骨牌不能相邻（上下左右）。使用小写拉丁字母表示颜色。输出任意一种可接受的铺法。 ## Input 输入包含一个正整数 $n$（$1 \leq n \leq 100$）——表示网格的列数。 ## Output 如果无解，输出 "-1"（不含引号）。否则，输出四行，每行包含 $n$ 个字符，描述一种铺法，其中每条垂直切割都至少穿过一个骨牌。你应使用不超过 $26$ 种颜色对铺法进行着色。每个骨牌应被赋予一种颜色，不同骨牌可以使用相同颜色，但相同颜色的骨牌不能相邻（上下左右）。使用小写拉丁字母表示颜色。输出任意一种可接受的铺法。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 100 $, denote the number of columns in a $ 4 \times n $ grid. A domino is a $ 1 \times 2 $ or $ 2 \times 1 $ rectangle covering exactly two adjacent unit squares. A *vertical cut* at position $ i \in \{1, \dots, n-1\} $ is the line between column $ i $ and column $ i+1 $. **Constraints** 1. The grid must be fully tiled by non-overlapping dominoes. 2. Each vertical cut at position $ i \in \{1, \dots, n-1\} $ must intersect at least one domino (i.e., no cut is "clean"—every cut must sever at least one domino). 3. Each square is covered by exactly one domino. 4. The tiling must be represented using at most 26 lowercase Latin letters as colors; each domino is assigned one color, and no two side-adjacent dominoes (sharing an edge) may share the same color. **Objective** If a valid tiling exists, output a $ 4 \times n $ grid of characters, where each character represents the color of the domino covering that square, satisfying the above constraints. If no such tiling exists, output "-1".

Samples

Input #1

Output #1

yyzz
bccd
bxxd
yyaa

API Response (JSON)

{
  "problem": {
    "name": "A. Domino",
    "description": {
      "content": "We all know the problem about the number of ways one can tile a 2 × _n_ field by 1 × 2 dominoes. You probably remember that it goes down to Fibonacci numbers. We will talk about some other problem bel",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF85A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We all know the problem about the number of ways one can tile a 2 × _n_ field by 1 × 2 dominoes. You probably remember that it goes down to Fibonacci numbers. We will talk about some other problem bel...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们都知道一个关于用 $1 \\times 2$ 多米诺骨牌铺满 $2 \\times n$ 网格的方案数的问题，你可能记得它归结为斐波那契数。下面我们讨论另一个问题，你同样需要使用多米诺骨牌铺满一个矩形区域。\n\n给定一个 $4 \\times n$ 的矩形区域，即包含四行和 $n$ 列的网格。你需要找到一种用 $1 \\times 2$ 多米诺骨牌铺满它的方案，使得每一条位于网格线上的潜在垂直切割（共 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 100 $, denote the number of columns in a $ 4 \\times n $ grid.  \nA domino is a $ 1 \\times 2 $ or $ 2 \\times 1 $ rectangle covering exactly tw...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments