← 返回题目列表

AtCoder · arc219_f

F. 范围划分

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

分数: 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.