/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に対して操作を 0 回以上行うことができます。1 回の操作では、以下の手順を順に行います：
- 以下の条件を全て満たす整数の組 (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
1 番目のテストケースについて考えます。
以下のように操作することで 5 回で 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) となる。
5 回未満の操作で A の要素を全て 0 にすることはできないので、5 を出力してください。
Score : 600 points
Problem Statement
You are given a sequence of non-negative integers A=(A_1,A_2,\ldots,A_N) of length N.
You can perform the following operation on A zero or more times. In one operation, perform the following steps in order:
- Choose a pair of integers (l,r) satisfying all of the following conditions:
- 1\le l\le r\le N
- A_l,A_{l+1},\ldots,A_r all have the same parity (that is, they are all even or all odd).
- For each k=l,l+1,\ldots,r, replace A_k with \displaystyle\left\lfloor\frac{A_k}2 \right\rfloor.
Find the minimum number of operations needed to make all elements of A equal to 0.
You are given T test cases; solve each of them.
Constraints
- 1\le T
- 1\le N\le 30
- 0\le A_i< 2^{60}
- The sum of N over all test cases is at most 30.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 A_2 \ldots A_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
4 2 9 12 3 3 1 2 1 0 7 6 28 24 18 12 22 1
Sample Output 1
5 3 0 10
Consider the first test case.
By performing operations as follows, all elements of A can be made 0 in five operations:
- Choose (l,r)=(1,1). A becomes (4,12).
- Choose (l,r)=(1,2). A becomes (2,6).
- Choose (l,r)=(1,2). A becomes (1,3).
- Choose (l,r)=(1,2). A becomes (0,1).
- Choose (l,r)=(2,2). A becomes (0,0).
It is impossible to make all elements of A equal to 0 in fewer than five operations, so output 5.