CF1453D Checkpoints

Gildong 正在开发一个包含 $n$ 个关卡的游戏，这些关卡从 $1$ 到 $n$ 依次编号。玩家从第 $1$ 关开始游戏，并且必须按照关卡编号递增的顺序依次通关。当玩家通过第 $n$ 关后，即视为胜利。 每个关卡最多有一个存档点，并且第 $1$ 关一定有存档点。在游戏开始时，只有第 $1$ 关的存档点被激活，其他所有存档点均未激活。当玩家到达带有存档点的第 $i$ 关时，该存档点会被激活。 每次尝试某一关时，玩家要么通过该关，要么失败。如果通过第 $i$ 关，玩家会进入第 $i+1$ 关。如果失败，则会被送回最近一次激活的存档点，并且需要重新挑战该存档点之后的所有关卡。 例如，假设 $n=4$，且第 $1$ 关和第 $3$ 关有存档点。玩家从第 $1$ 关开始。如果在第 $1$ 关失败，则需要重新尝试第 $1$ 关，因为第 $1$ 关的存档点是最近一次激活的存档点。如果通过第 $1$ 关，则进入第 $2$ 关。如果在第 $2$ 关失败，则又会被送回第 $1$ 关。如果连续通过第 $1$ 关和第 $2$ 关，则进入第 $3$ 关，并激活第 $3$ 关的存档点。此后，无论在第 $3$ 关还是通过第 $3$ 关后在第 $4$ 关失败，都会被送回第 $3$ 关。如果连续通过第 $3$ 关和第 $4$ 关，则胜利通关。 Gildong 打算让所有关卡的难度相同。他希望你能设计一组关卡和存档点（最多 $2000$ 关），使得对于每一关通过概率恰好为 $\frac{1}{2}$ 的玩家来说，所有关卡的期望尝试次数恰好为 $k$。

每组测试数据包含一个或多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。 每个测试用例恰好一行，包含一个整数 $k$（$1 \le k \le 10^{18}$），表示 Gildong 希望玩家在通过所有关卡时的期望尝试次数（每一关通过概率为 $\frac{1}{2}$）。

对于每个测试用例，如果无法用不超过 $2000$ 个关卡构造出满足条件的关卡和存档点，请输出 $-1$。 否则，输出两行。第一行包含一个整数 $n$（$1 \le n \le 2000$），表示关卡数。第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 关是否有存档点。如果第 $i$ 关没有存档点，则为 $0$，有存档点则为 $1$。注意，根据题意，第一个整数必须为 $1$。

在第一个和第二个样例中，最“简单”的关卡序列是只有 $1$ 关且有存档点。这种情况下期望尝试次数已经是 $2$，因此无法让期望尝试次数为 $1$。 在第三个样例中，每一关的期望尝试次数为 $2$，并且玩家每次失败都可以直接重试该关，不会回到前面的关卡。因此，总的期望尝试次数为 $8$。注意，也存在使用更少关卡的答案，但你不需要最小化关卡数。 由 ChatGPT 4.1 翻译