← 返回题目列表

Codeforces · 1762/A

A. 分而治之

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

如果 $$$b$$$ 的元素总和是偶数,则数组 $$$b$$$ 是好的。

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。在一次操作中,您可以选择索引 $$$i$$$ 并更改 $$$a_i := \lfloor \frac{a_i}{2} \rfloor$$$。 $$$^\匕首$$$

找出使 $$$a$$$ 良好所需的最少操作数(可能是 $$$0$$$)。可以证明,总是有可能使 $$$a$$$ 变得更好。

$$$^\dagger$$$ $$$\lfloor x \rfloor$$$ 表示下限函数 - 小于或等于 $$$x$$$ 的最大整数。例如,$$$\lfloor 2.7 \rfloor = 2$$$、$$$\lfloor \pi \rfloor = 3$$$ 和 $$$\lfloor 5 \rfloor =5$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — 表示数组 $$$a$$$。

请注意,所有测试用例的 $$$n$$$ 之和是没有界限的。

输出

对于每个测试用例,输出使 $$$a$$$ 良好所需的最少操作数。

示例

输入 #1

4
4
1 1 1 1
2
7 4
3
1 2 4
1
15

输出 #1

0
2
1
4

注意

在第一个测试用例中,数组 $$$a$$$ 已经很好了。

在第二个测试用例中,我们可以对索引 $$$2$$$ 执行两次。第一次操作后,数组 $$$a$$$ 变为 $$$[7,2]$$$。再次对索引 $$$2$$$ 执行后,$$$a$$$ 变为 $$$[7,1]$$$,这很好。可以证明,不可能用较少的操作次数就使 $$$a$$$ 变得很好。

在第三个测试用例中,如果我们对索引 $$$1$$$ 执行一次操作,则 $$$a$$$ 变为 $$$[0,2,4]$$$ 。由于 $$$[0,2,4]$$$ 很好,答案是 $$$1$$$。

在第四个测试用例中,我们需要对索引 $$$1$$$ 执行四次操作。完成所有操作后,$$$a$$$ 变为$$$[0]$$$。可以证明,不可能用较少的操作次数就使 $$$a$$$ 变得很好。