E. Ugly Polyomino

Codeforces

IDCF10157E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Полимино — это связная фигура из n равных квадратов, соединённых сторонами. Неформально, это связное множество клеток, которое можно вырезать из бесконечного листа клетчатой бумаги. Два полимино считаются совпадающими, если одно из них можно перевести в другое с помощью параллельных переносов, поворотов или отражений относительно прямой, параллельной одной из осей координат (которым параллельны все стороны всех квадратиков). Набор n-полимино считается полным, если никакие два полимино в наборе не являются совпадающими и любое добавленное в набор n-полимино будет совпадать с каким-нибудь из имеющихся. Например, полный набор 3-полимино состоит из двух фигур, а полный набор 4-полимино состоит из пяти фигур. У Алёны есть полный набор n-полимино. Она считает _некрасивыми_ все полимино, содержащие квадрат 2 × 2. По заданному n определите количество некрасивых полимино. Первая строка входа содержит одно целое число n — параметр набора полимино (3 ≤ n ≤ 7). Выведите одно целое число — количество некрасивых n-полимино. Так как в квадрате 2 × 2 4 клетки, а в 3-полимино 3 клетки, то ни одно 3-полимино не содержит квадрата 2 × 2. Единственным 4-полимино, содержащим квадрат 2 × 2, является сам квадрат 2 × 2. ## Входные Данные Первая строка входа содержит одно целое число n — параметр набора полимино (3 ≤ n ≤ 7). ## Выходные Данные Выведите одно целое число — количество некрасивых n-полимино. ## Примеры Входные данные3Выходные данные0Входные данные4Выходные данные1 ## Примечание Так как в квадрате 2 × 2 4 клетки, а в 3-полимино 3 клетки, то ни одно 3-полимино не содержит квадрата 2 × 2.Единственным 4-полимино, содержащим квадрат 2 × 2, является сам квадрат 2 × 2. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 7 $. Let $ \mathcal{P}_n $ be the complete set of $ n $-polyominoes, where each element is a connected set of $ n $ unit squares joined edge-to-edge, up to translation, rotation, and reflection. **Constraints** 1. $ |\mathcal{P}_n| $ is finite and known for $ n \in \{3, 4, 5, 6, 7\} $. 2. A polyomino $ P \in \mathcal{P}_n $ is *ugly* if it contains a $ 2 \times 2 $ block of squares (i.e., four squares forming a solid square). **Objective** Compute the number of ugly $ n $-polyominoes: $$ \left| \left\{ P \in \mathcal{P}_n \mid P \text{ contains a } 2 \times 2 \text{ block} \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "E. Ugly Polyomino",
    "description": {
      "content": "Полимино — это связная фигура из n равных квадратов, соединённых сторонами. Неформально, это связное множество клеток, которое можно вырезать из бесконечного листа клетчатой бумаги. Два полимино счита",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10157E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Полимино — это связная фигура из n равных квадратов, соединённых сторонами. Неформально, это связное множество клеток, которое можно вырезать из бесконечного листа клетчатой бумаги. Два полимино счита...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 7 $.  \nLet $ \\mathcal{P}_n $ be the complete set of $ n $-polyominoes, where each element is a connected set of $ n $ unit squares joine...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments