分数: 600 点
问题陈述
给你一个非负整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
您可以对 A 零次或多次。在一次操作中,按顺序执行以下步骤:
- 选择一对整数 (l,r) 满足以下所有条件:
- 1\le l\le r\le N
- A_l,A_{l+1},\ldots,A_r 都具有相同的奇偶性(即,它们都是偶数或都是奇数)。
- 对于每个 k=l,l+1,\ldots,r,替换 A_k 与 \displaystyle\left\lfloor\frac{A_k}2 \right\rfloor.
找出使所有元素成为所需的最少操作数 A 等于 0.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T
- 1\le N\le 30
- 0\le A_i< 2^{60}
- 总和 N 所有测试用例最多 30.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N A_1 A_2 \ldots A_N
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
4 2 9 12 3 3 1 2 1 0 7 6 28 24 18 12 22 1
示例输出 1
5 3 0 10
考虑第一个测试用例。
通过执行如下操作,所有元素 A 可以制作 0 五次操作:
- 选择 (l,r)=(1,1). A 变为 (4,12).
- 选择 (l,r)=(1,2). A 变为 (2,6).
- 选择 (l,r)=(1,2). A 变为 (1,3).
- 选择 (l,r)=(1,2). A 变为 (0,1).
- 选择 (l,r)=(2,2). A 变为 (0,0).
不可能使所有元素 A 等于 0 少于五次操作,因此输出 5.