← 返回题目列表

Codeforces · 1938/C

C. 位计数序列

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

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Bit Counting Sequence - 原题 PDF 第 1 页
原题PDF第5页
Bit Counting Sequence - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
Problem C
                      Bit Counting Sequence
                     Time limit: 2 seconds


For a non-negative integer x, let p(x) be the number of ones in the binary representation of x. For example, p(26) = 3
because 26 = (11010)2.

You are given a sequence of n integers (a1, a2, . . . , an). Your task is to determine whether there exists a non-negative
integer x such that (p(x), p(x + 1), ..., p(x + n −1)) is equal to (a1, a2, . . . , an). Furthermore, if it exists, compute
the smallest x satisfying the condition.

Input

The first line of input contains one integer t (1 ≤t ≤1000) representing the number of test cases. After that, t test
cases follow. Each of them is presented as follows.

The first line contains one integer n (1 ≤n ≤500 000). The second line contains n integers a1, a2, . . . , an (0 ≤ai ≤
60 for all i).

The sum of n across all test cases in one input file does not exceed 500 000.

Output

For each test case, output the smallest non-negative integer x satisfying the condition above.  If there is no such x,
output -1 instead.


 Sample Input #1                          Sample Output #1
 4                                      13
 5                                      3
 3 3 4 1 2                              2305843009213693949
 3                                      -1
 2 1 2
 2
 60 60
 2
 8 0


Explanation for the sample input/output #1

For the first test case, x = 13 satisfies the condition above since (p(13), p(14), p(15), p(16), p(17)) = (3, 3, 4, 1, 2).
It can be shown that there is no non-negative integer smaller than 13 that satisfies the condition above.





ICPC Asia Pacific Championship 2024 Problem C: Bit Counting Sequence

This page is intentionally left blank.





ICPC Asia Pacific Championship 2024 Problem C: Bit Counting Sequence