『GROI-R2』 记忆碎片

记忆的碎片散落在各个角落，而爱丽丝想把它们拼合在一起。 碎片的顺序是给定的，因为记忆显然不能反过来进行。但是，碎片各自的形状和内容是可以打磨和修正的——毕竟所有人的记忆都会歪曲和遗忘。 每个碎片上的记忆都可以用一个**非负整数**来表示。而相邻的两个碎片能够完整地拼合起来，当且仅当它们记忆的和是一个**完全平方数**。 现在，爱丽丝可以打磨若干块碎片，使得每一对相邻的碎片都能够完整地拼合起来。对于每一次打磨，爱丽丝可以选择一块碎片，将这块碎片上的记忆修改为任意一个**非负整数**。爱丽丝想知道，她至少要打磨多少块碎片，才能实现她的目标。同时，她还希望你给出打磨之后，每块碎片上留有的记忆是多少。 **形式化题面** 给定一个**非负整数**序列 $\{a_n\}$，我们定义一次操作是任意选择一个 $i\in [1,n]$ 并将 $a_i$ 改为任意一个**非负整数** $x$。 问至少进行几次操作才可以满足 $\forall i\in [1,n-1]$ 有 $a_i+a_{i+1}$ 为**完全平方数**，并给出修改方案。 ## Input 第一行输入一个整数 $n$，表示记忆碎片的个数。 第二行输入一个长度为 $n$ 的非负整数序列 $a$，表示每个记忆碎片上的记忆。 ## Output 第一行输出一个整数，表示最少打磨次数。 第二行输出一个长度为 $n$ 的整数序列，表示所有打磨过后的记忆碎片上的记忆。 你必须保证你打磨后的记忆满足题目条件，且与你给出的最少打磨次数相符，并满足每个碎片上的记忆都在 $[0,10^{18}]$ 的范围内。 [samples] ## Note **样例解释** 对于第一组样例，不难证明爱丽丝至少要打磨一块碎片才能使所有的记忆满足条件。 请一定注意记忆碎片的顺序是不能改变的。 **评分规则** 如果你对于某一测试点输出的最少打磨次数是正确的，你将获得该测试点 $30\%$ 的分数。 如果你在最少打磨次数正确的基础上给出了正确的构造，你将获得该测试点 $100\%$ 的分数。 如果你只会求解最少打磨次数，那也请你在第二行输出以空格隔开的 $n$ 个在 $[0,10^{18}]$ 范围内的整数，否则可能被判为 $0$ 分。 请注意，你在每个 subtask 中得到的 $30\%$ 分数会被下取整计算。 **数据范围** **本题采用捆绑测试**。 | $\text{Subtask}$ | $n\le$ | $a_i\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $2$ | $10^8$ | | $5$ | | $2$ | $3$ | $10^8$ | | $20$ | | $3$ | $4$ | $10^8$ | | $15$ | | $4$ | $10^3$ | $10^8$ | | $15$ | | $5$ | $10^6$ | $10^4$ | | $10$ | | $6$ | $10^6$ | $10^8$ | $\text{A}$ | $10$ | | $7$ | $10^6$ | $10^8$ | | $25$ | 特殊性质 $\text{A}$：$\forall 1\le i,j\le n$ 满足 $a_i=a_j$。 对于 $100\%$ 的数据满足 $1\le n\le 10^6$，$0\le a_i\le 10^8$。