← 返回题目列表

Codeforces · 1661/B

B. 归零

中文机器翻译题面 查看原题

假设您有一个整数 $$$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$$$ 所需的最少操作数。

示例

输入 #1

4
19 32764 10240 49

输出 #1

14 4 4 15

注意

让我们考虑每个 $$$a_i$$$:

- $$$a_1 = 19$$$。首先,您可以将其加一以获得 $$$20$$$,然后将其乘以两倍 $$$13$$$ 倍。您将在 $$$1 + 13 = 14$$$ 步骤中获得 $$$0$$$。
- $$$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$$$ 倍。