CF1661B Getting Zero

假设你有一个整数 $v$。每次操作，你可以： - 将 $v$ 设为 $(v + 1) \bmod 32768$； - 或将 $v$ 设为 $(2 \cdot v) \bmod 32768$。 现在给定 $n$ 个整数 $a_1, a_2, \dots, a_n$。你需要求出将每个 $a_i$ 变为 $0$ 所需的最少操作次数。

第一行包含一个整数 $n$（$1 \le n \le 32768$），表示整数的个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 32768$）。

输出 $n$ 个整数，第 $i$ 个整数表示将 $a_i$ 变为 $0$ 所需的最少操作次数。

我们来考虑每个 $a_i$： - $a_1 = 19$。你可以先加一得到 $20$，然后乘二 $13$ 次。总共需要 $1 + 13 = 14$ 步。 - $a_2 = 32764$。你可以加一 $4$ 次：$32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$。 - $a_3 = 10240$。你可以乘二 $4$ 次：$10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$。 - $a_4 = 49$。你可以乘二 $15$ 次。 由 ChatGPT 4.1 翻译