C. Make a Square

Codeforces

IDCF962C

Time2000ms

Memory256MB

Difficulty—

brute forceimplementationmath

English · Original

Chinese · Translation

Formal · Original

You are given a positive integer $n$, written without leading zeroes (for example, the number _04_ is incorrect). In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros. Determine the minimum number of operations that you need to consistently apply to the given integer $n$ to make from it the square of some positive integer or report that it is impossible. An integer $x$ is the square of some positive integer if and only if $x=y^2$ for some positive integer $y$. ## Input The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{9}$). The number is given without leading zeroes. ## Output If it is impossible to make the square of some positive integer from $n$, print _\-1_. In the other case, print the minimal number of operations required to do it. [samples] ## Note In the first example we should delete from $8314$ the digits $3$ and $4$. After that $8314$ become equals to $81$, which is the square of the integer $9$. In the second example the given $625$ is the square of the integer $25$, so you should not delete anything. In the third example it is impossible to make the square from $333$, so the answer is _\-1_.

给你一个正整数 $n$，其十进制表示中不包含前导零（例如，数字 _04_ 是无效的）。在一次操作中，你可以删除该整数的任意一位数字，使得结果仍为一个不含前导零的正整数。请确定最少需要多少次操作，才能通过连续删除数字，使 $n$ 变为某个正整数的平方；若不可能，则报告不可能。一个整数 $x$ 是某个正整数的平方，当且仅当存在正整数 $y$ 使得 $x = y^2$。第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^9$）。该数以无前导零的形式给出。如果无法从 $n$ 得到某个正整数的平方，请输出 _-1_；否则，输出所需的最少操作次数。 ## Input 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^9$）。该数以无前导零的形式给出。 ## Output 如果无法从 $n$ 得到某个正整数的平方，请输出 _-1_；否则，输出所需的最少操作次数。 [samples] ## Note 在第一个例子中，我们需要从 $8314$ 中删除数字 $3$ 和 $4$。删除后，$8314$ 变为 $81$，它是整数 $9$ 的平方。在第二个例子中，给定的 $625$ 是整数 $25$ 的平方，因此无需删除任何数字。在第三个例子中，无法从 $333$ 得到任何平方数，因此答案为 _-1_。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the input integer, represented as a string of digits $ d_1 d_2 \dots d_k $ with $ k = \lfloor \log_{10} n \rfloor + 1 $, $ d_1 \neq 0 $, and no leading zeros. Let $ S \subseteq \{1, 2, \dots, k\} $ be a subset of indices corresponding to digits retained in a subsequence of $ n $. Let $ \text{subseq}(S) $ denote the positive integer formed by the digits $ d_i $ for $ i \in S $, in order, with $ d_{\min S} \neq 0 $ (to avoid leading zeros). Let $ \mathcal{Q} = \{ y^2 \mid y \in \mathbb{Z}^+ \} $ be the set of perfect squares. **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^9 $ 2. Any retained subsequence must form a positive integer (no leading zeros). 3. Only digit deletions are allowed; digit order must be preserved. **Objective** Find the minimum number of deletions $ m \in \mathbb{Z}_{\geq 0} $ such that $ \text{subseq}(S) \in \mathcal{Q} $ for some subset $ S \subseteq \{1, \dots, k\} $ with $ |S| = k - m $, or return $ -1 $ if no such $ S $ exists. Equivalently, minimize $ m = k - |S| $ over all $ S \subseteq \{1, \dots, k\} $ such that $ \text{subseq}(S) \in \mathcal{Q} $ and $ \text{subseq}(S) > 0 $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Make a Square",
    "description": {
      "content": "You are given a positive integer $n$, written without leading zeroes (for example, the number _04_ is incorrect). In one operation you can delete any digit of the given integer so that the result rem",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF962C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer $n$, written without leading zeroes (for example, the number _04_ is incorrect).\n\nIn one operation you can delete any digit of the given integer so that the result rem...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一个正整数 $n$，其十进制表示中不包含前导零（例如，数字 _04_ 是无效的）。 \n\n在一次操作中，你可以删除该整数的任意一位数字，使得结果仍为一个不含前导零的正整数。\n\n请确定最少需要多少次操作，才能通过连续删除数字，使 $n$ 变为某个正整数的平方；若不可能，则报告不可能。\n\n一个整数 $x$ 是某个正整数的平方，当且仅当存在正整数 $y$ 使得 $x = y^2$。\n\n第一行包含一个整...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the input integer, represented as a string of digits $ d_1 d_2 \\dots d_k $ with $ k = \\lfloor \\log_{10} n \\rfloor + 1 $, $ d_1 \\neq 0 $, and no leading ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments