Divide and Conquer

题意翻译

我们称一个序列 $b$ 是好的仅当 $b$ 中元素和为偶数。 给你一个长度为 $n$ 的正整数序列 $a$。每次你可以任意选择一个 $i$，使 $a_i$ 变为 $\left\lfloor\dfrac{a_i}{2}\right\rfloor$。 求最少多少次操作才能让序列 $a$ 变为好的（可能是 $0$ 次）。 $t$ 组数据。$1\le t\le 1000,1\le n\le 50,1\le a_i\le 10^6$。

题目描述

An array $ b $ is good if the sum of elements of $ b $ is even. You are given an array $ a $ consisting of $ n $ positive integers. In one operation, you can select an index $ i $ and change $ a_i := \lfloor \frac{a_i}{2} \rfloor $ . $ ^\dagger $ Find the minimum number of operations (possibly $ 0 $ ) needed to make $ a $ good. It can be proven that it is always possible to make $ a $ good. $ ^\dagger $ $ \lfloor x \rfloor $ denotes the floor function — the largest integer less than or equal to $ x $ . For example, $ \lfloor 2.7 \rfloor = 2 $ , $ \lfloor \pi \rfloor = 3 $ and $ \lfloor 5 \rfloor =5 $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 50 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ space-separated integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \leq a_i \leq 10^6 $ ) — representing the array $ a $ . Do note that the sum of $ n $ over all test cases is not bounded.

输出格式

For each test case, output the minimum number of operations needed to make $ a $ good.

输入输出样例

输入样例 #1

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

输出样例 #1

0
2
1
4

说明

In the first test case, array $ a $ is already good. In the second test case, we can perform on index $ 2 $ twice. After the first operation, array $ a $ becomes $ [7,2] $ . After performing on index $ 2 $ again, $ a $ becomes $ [7,1] $ , which is good. It can be proved that it is not possible to make $ a $ good in less number of operations. In the third test case, $ a $ becomes $ [0,2,4] $ if we perform the operation on index $ 1 $ once. As $ [0,2,4] $ is good, answer is $ 1 $ . In the fourth test case, we need to perform the operation on index $ 1 $ four times. After all operations, $ a $ becomes $ [0] $ . It can be proved that it is not possible to make $ a $ good in less number of operations.

题目大意：
一个序列 $b$ 是好的当且仅当 $b$ 中元素的和为偶数。给定一个长度为 $n$ 的正整数序列 $a$，每次可以选择一个 $i$，使得 $a_i$ 变为 $\left\lfloor\dfrac{a_i}{2}\right\rfloor$。求最少需要多少次操作才能使得序列 $a$ 变为好的（可能是 $0$ 次）。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $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$。

输出格式：
- 对于每个测试用例，输出使序列 $a$ 变为好的所需的最少操作次数。

输入输出样例：
输入样例 #1：
```
4
4
1 1 1 1
2
7 4
3
1 2 4
1
15
```
输出样例 #1：
```
0
2
1
4
```题目大意： 一个序列 $b$ 是好的当且仅当 $b$ 中元素的和为偶数。给定一个长度为 $n$ 的正整数序列 $a$，每次可以选择一个 $i$，使得 $a_i$ 变为 $\left\lfloor\dfrac{a_i}{2}\right\rfloor$。求最少需要多少次操作才能使得序列 $a$ 变为好的（可能是 $0$ 次）。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $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$。 输出格式： - 对于每个测试用例，输出使序列 $a$ 变为好的所需的最少操作次数。 输入输出样例： 输入样例 #1： ``` 4 4 1 1 1 1 2 7 4 3 1 2 4 1 15 ``` 输出样例 #1： ``` 0 2 1 4 ```