{"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 remains a positive integer without leading zeros.\n\nDetermine 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.\n\nAn integer $x$ is the square of some positive integer if and only if $x=y^2$ for some positive integer $y$.\n\n## Input\n\nThe first line contains a single integer $n$ ($1 \\le n \\le 2 \\cdot 10^{9}$). The number is given without leading zeroes.\n\n## Output\n\nIf 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.\n\n[samples]\n\n## Note\n\nIn 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$.\n\nIn the second example the given $625$ is the square of the integer $25$, so you should not delete anything.\n\nIn the third example it is impossible to make the square from $333$, so the answer is _\\-1_.","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第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^9$）。该数以无前导零的形式给出。\n\n如果无法从 $n$ 得到某个正整数的平方，请输出 _-1_；否则，输出所需的最少操作次数。\n\n## Input\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 2 dot.op 10^9$）。该数以无前导零的形式给出。\n\n## Output\n\n如果无法从 $n$ 得到某个正整数的平方，请输出 _-1_；否则，输出所需的最少操作次数。\n\n[samples]\n\n## Note\n\n在第一个例子中，我们需要从 $8314$ 中删除数字 $3$ 和 $4$。删除后，$8314$ 变为 $81$，它是整数 $9$ 的平方。在第二个例子中，给定的 $625$ 是整数 $25$ 的平方，因此无需删除任何数字。在第三个例子中，无法从 $333$ 得到任何平方数，因此答案为 _-1_。","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 zeros.  \nLet $ S \\subseteq \\{1, 2, \\dots, k\\} $ be a subset of indices corresponding to digits retained in a subsequence of $ n $.  \nLet $ \\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).  \n\nLet $ \\mathcal{Q} = \\{ y^2 \\mid y \\in \\mathbb{Z}^+ \\} $ be the set of perfect squares.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^9 $  \n2. Any retained subsequence must form a positive integer (no leading zeros).  \n3. Only digit deletions are allowed; digit order must be preserved.\n\n**Objective**  \nFind 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.  \n\nEquivalently, minimize $ m = k - |S| $ over all $ S \\subseteq \\{1, \\dots, k\\} $ such that $ \\text{subseq}(S) \\in \\mathcal{Q} $ and $ \\text{subseq}(S) > 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF962C","tags":["brute force","implementation","math"],"sample_group":[["8314","2"],["625","0"],["333","\\-1"]],"created_at":"2026-03-03 11:00:39"}}