← 返回题目列表

Codeforces · 1490/A

A. 密集阵列

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

如果任何两个相邻元素中较大的元素不大于较小元素的两倍,则 Polycarp 称数组为密集的。更正式地说,对于任何 $$$i$$$ ($$$1 \le i \le n-1$$$),必须满足以下条件: $$$$$$\frac{\max(a[i], a[i+1])}{\min(a[i], a[i+1])} \le 2$$$$$$

例如,数组 $$$[1, 2, 3, 4, 3]$$$、$$$[1, 1, 1]$$$ 和 $$$[5, 10]$$$ 是稠密的。并且数组 $$$[5, 11]$$$, $$$[1, 4, 2]$$$, $$$[6, 6, 1]$$$ 并不稠密。

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。要使数组变得稠密,您至少需要添加多少个数字?您可以在数组中的任意位置插入数字。如果数组已经很稠密,则无需添加数字。

例如,如果 $$$a=[4,2,10,1]$$$,那么答案是 $$$5$$$,插入元素后的数组本身可能如下所示: $$$a=[4,2,\underline{\textbf{3}},\underline{\textbf{5}},10,\underline{\textbf{6}},\underline{\textbf{4}},\underline{\textbf{2}},1]$$$(还有其他方法来构建这样的$$$a$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$)。然后是 $$$t$$$ 测试用例。

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

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 50$$$)。

输出

对于每个测试用例,输出一个整数 - 必须添加到数组以使其稠密的最小数字数。

示例

输入 #1

6
4
4 2 10 1
2
1 3
2
6 1
3
1 4 2
5
1 2 3 4 3
12
4 31 25 50 30 20 34 46 42 16 15 16

输出 #1

5
1
2
1
0
3

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,您可以插入一个元素,$$$a=[1,\underline{\textbf{2}},3]$$$。

在第三个测试用例中,您可以插入两个元素,$$$a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]$$$。

在第四个测试用例中,您可以插入一个元素,$$$a=[1,\underline{\textbf{2}},4,2]$$$。

在第五个测试用例中,数组 $$$a$$$ 已经是稠密的。