M. Matrix, The

Codeforces

IDCF10091M

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

...Neo finally understood how The Matrix is working. The Matrix is the square grid n × n; each cell of the grid contains 0 or 1. Next additional limitations are working for The Matrix: The Matrix changes with time following next law: lets define #cf_span(class=[tex-font-style-underline], body=[state]) of The Matrix as sequence of n2 elements (a1, 1, ..., a1, n, a2, 1, ..., an, n), obtained from The Matrix by writing all its lines one by one. Then all states, corresponding to correct (i.e. conforming with limitations above) instances of The Matrix, are ordered lexicographcally and in time t The Matrix have t-th state in the resulting list. Neo is sure that he can reconstruct the Matrix in any moment of time. Can you do it? First line of the input contains four integers n, a, b and q (1 ≤ n ≤ 10, 1 ≤ a ≤ b ≤ n, 1 ≤ q ≤ 1000) — dimension of The Matrix, parameters of The Matrix and number of queries, respectively. i-th of the next q lines contains one integer ti — some moment of time (1 ≤ ti ≤ 1018). For i-th request print n lines, each containing n characters — The Matrix in the time ti. If total number of correct instances of the Matrix is less than ti, print "_No such matrix._" without quotes. Separate answers on different requests with newline. Follow the sample for clarify. ## Input First line of the input contains four integers n, a, b and q (1 ≤ n ≤ 10, 1 ≤ a ≤ b ≤ n, 1 ≤ q ≤ 1000) — dimension of The Matrix, parameters of The Matrix and number of queries, respectively. i-th of the next q lines contains one integer ti — some moment of time (1 ≤ ti ≤ 1018). ## Output For i-th request print n lines, each containing n characters — The Matrix in the time ti. If total number of correct instances of the Matrix is less than ti, print "_No such matrix._" without quotes. Separate answers on different requests with newline. Follow the sample for clarify. [samples]

**Definitions** Let $ n, a, b, q \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10 $, $ 1 \leq a \leq b \leq n $, $ 1 \leq q \leq 1000 $. Let $ \mathcal{M} $ be the set of all $ n \times n $ binary matrices (entries in $ \{0,1\} $) such that the number of 1s in each row is in $ [a, b] $. Let $ S \subseteq \{0,1\}^{n^2} $ be the set of all lexicographically ordered state vectors obtained by flattening matrices in $ \mathcal{M} $ row-wise. **Constraints** 1. $ |S| = \left( \sum_{k=a}^{b} \binom{n}{k} \right)^n $ 2. For each query time $ t_i \in \mathbb{Z} $, $ 1 \leq t_i \leq 10^{18} $ **Objective** For each query $ t_i $: - If $ t_i > |S| $, output "_No such matrix._" - Else, output the $ t_i $-th lexicographically smallest matrix in $ S $, formatted as $ n $ lines of $ n $ characters (0 or 1).

API Response (JSON)

{
  "problem": {
    "name": "M. Matrix, The",
    "description": {
      "content": "...Neo finally understood how The Matrix is working. The Matrix is the square grid n × n; each cell of the grid contains 0 or 1. Next additional limitations are working for The Matrix: The Matrix ch",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10091M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "...Neo finally understood how The Matrix is working.\n\nThe Matrix is the square grid n × n; each cell of the grid contains 0 or 1. Next additional limitations are working for The Matrix:\n\nThe Matrix ch...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, a, b, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10 $, $ 1 \\leq a \\leq b \\leq n $, $ 1 \\leq q \\leq 1000 $.  \nLet $ \\mathcal{M} $ be the set of all $ n \\times n $ binary matri...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments