C. Constructing Tests

Codeforces

IDCF938C

Time1000ms

Memory256MB

Difficulty—

binary searchbrute forceconstructive algorithms

English · Original

Chinese · Translation

Formal · Original

Let's denote a _m_\-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size _m_ × _m_ of this matrix contains at least one zero. Consider the following problem: _You are given two integers _n_ and _m_. You have to construct an _m_\-free square matrix of size _n_ × _n_ such that **the number of 1's in this matrix is maximum possible**. Print the maximum possible number of 1's in such matrix._ You don't have to solve this problem. Instead, you have to construct a few tests for it. You will be given _t_ numbers _x_1, _x_2, ..., _x__t_. For every , find two integers _n__i_ and _m__i_ (_n__i_ ≥ _m__i_) such that the answer for the aforementioned problem is exactly _x__i_ if we set _n_ = _n__i_ and _m_ = _m__i_. ## Input The first line contains one integer _t_ (1 ≤ _t_ ≤ 100) — the number of tests you have to construct. Then _t_ lines follow, _i_\-th line containing one integer _x__i_ (0 ≤ _x__i_ ≤ 109). **Note that in hacks you have to set _t_ = 1**. ## Output For each test you have to construct, output two positive numbers _n__i_ and _m__i_ (1 ≤ _m__i_ ≤ _n__i_ ≤ 109) such that the maximum number of 1's in a _m__i_\-free _n__i_ × _n__i_ matrix is exactly _x__i_. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer - 1. [samples]

我们定义一个 #cf_span[m]-free 矩阵为一个二进制矩阵（仅由 #cf_span[1] 和 #cf_span[0] 组成），使得该矩阵的每一个大小为 #cf_span[m × m] 的子方阵都至少包含一个零。考虑以下问题： _给你两个整数 #cf_span[n] 和 #cf_span[m]。你需要构造一个大小为 #cf_span[n × n] 的 #cf_span[m]-free 矩阵，使得该矩阵中 #cf_span[1] 的数量尽可能多。请输出此类矩阵中 #cf_span[1] 的最大可能数量。_ 你不需要解决这个问题。相反，你需要为这个问题构造一些测试用例。你将得到 #cf_span[t] 个数 #cf_span[x1], #cf_span[x2], ..., #cf_span[xt]。对于每个 #cf_span[xi]，找出两个整数 #cf_span[ni] 和 #cf_span[mi]（#cf_span[ni ≥ mi]），使得当我们将 #cf_span[n = ni] 和 #cf_span[m = mi] 代入上述问题时，答案恰好为 #cf_span[xi]。第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 100]）——你需要构造的测试用例数量。接下来 #cf_span[t] 行，第 #cf_span[i] 行包含一个整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ 10^9]）。 *注意：在 Hack 中，你必须设置 #cf_span[t = 1]*。对于每个你需要构造的测试用例，输出两个正整数 #cf_span[ni] 和 #cf_span[mi]（#cf_span[1 ≤ mi ≤ ni ≤ 10^9]），使得在 #cf_span[mi]-free 的 #cf_span[ni × ni] 矩阵中，#cf_span[1] 的最大数量恰好为 #cf_span[xi]。如果有多个解，你可以输出任意一个；如果无法构造这样的测试用例，则输出单个整数 #cf_span[-1]。 ## Input 第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 100]）——你需要构造的测试用例数量。然后 #cf_span[t] 行，第 #cf_span[i] 行包含一个整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ 10^9]）。*注意：在 Hack 中，你必须设置 #cf_span[t = 1]*。 ## Output 对于每个你需要构造的测试用例，输出两个正整数 #cf_span[ni] 和 #cf_span[mi]（#cf_span[1 ≤ mi ≤ ni ≤ 10^9]），使得在 #cf_span[mi]-free 的 #cf_span[ni × ni] 矩阵中，#cf_span[1] 的最大数量恰好为 #cf_span[xi]。如果有多个解，你可以输出任意一个；如果无法构造这样的测试用例，则输出单个整数 #cf_span[-1]。 [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. Let $ X = \{x_1, x_2, \dots, x_t\} \subseteq \mathbb{Z}_{\geq 0} $ be the given target values. **Constraints** 1. $ 1 \leq t \leq 100 $ 2. For each $ i \in \{1, \dots, t\} $, $ 0 \leq x_i \leq 10^9 $ **Objective** For each $ x_i \in X $, find integers $ n_i, m_i \in \mathbb{Z} $ such that: - $ 1 \leq m_i \leq n_i \leq 10^9 $, - The maximum number of $ 1 $'s in an $ m_i $-free $ n_i \times n_i $ binary matrix equals $ x_i $. If no such $ (n_i, m_i) $ exists, output $ -1 $.

Samples

Input #1

Output #1

5 2
1 1
-1

API Response (JSON)

{
  "problem": {
    "name": "C. Constructing Tests",
    "description": {
      "content": "Let's denote a _m_\\-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size _m_ × _m_ of this matrix contains at least one zero. Consider the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF938C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let's denote a _m_\\-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size _m_ × _m_ of this matrix contains at least one zero.\n\nConsider the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们定义一个 #cf_span[m]-free 矩阵为一个二进制矩阵（仅由 #cf_span[1] 和 #cf_span[0] 组成），使得该矩阵的每一个大小为 #cf_span[m × m] 的子方阵都至少包含一个零。\n\n考虑以下问题：\n\n_给你两个整数 #cf_span[n] 和 #cf_span[m]。你需要构造一个大小为 #cf_span[n × n] 的 #cf_span[m]-free...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ X = \\{x_1, x_2, \\dots, x_t\\} \\subseteq \\mathbb{Z}_{\\geq 0} $ be the given target values.  \n\n**Constraints**  \n1. $ 1 \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments