/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数 X に対し，「 X を 2 進法表記したときに現れる 1 の個数」を f(X) とします． たとえば，6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)} なので，f(6) = 2, \ f(11) = 3, \ f(16) = 1 です．
正整数 N が与えられます． N 以下の正整数 X であって，f(X) = 3 を満たすものが存在するかどうかを判定し，存在するならその最大値を求めてください．
T 個のテストケースが与えられるので，それぞれについて答えてください．
制約
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる． N_i は i 番目のテストケースにおける N の値を表す．
T N_1 N_2 \vdots N_T
出力
T 行出力せよ．
i 行目には，N_i 以下の正整数 X であって，f(X) = 3 を満たすものの最大値を出力せよ．
ただし，そのような正整数 X が存在しない場合には -1 を出力せよ．
入力例 1
4 16 161 4 1000000000000000000
出力例 1
14 161 -1 936748722493063168
- 1 つ目のテストケースについて，f(14) = 3, \ f(15) = 4, \ f(16) = 1 なので，X \leq 16 かつ f(X) = 3 を満たす最大の正整数 X は 14 です．
- 2 つ目のテストケースについて，f(161) = 3 なので，X \leq 161 かつ f(X) = 3 を満たす最大の正整数 X は 161 です．
- 3 つ目のテストケースについて，f(1) = 1, \ f(2) = 1, \ f(3) = 2, \ f(4) = 1 なので，X \leq 4 かつ f(X) = 3 を満たす正整数 X は存在しません．
- 4 つ目のテストケースのように，入出力値が 32bit 整数型に収まらないこともあります．
Score : 400 points
Problem Statement
For a positive integer X, let f(X) be the number of 1s that appear when X is represented in binary notation. For example, 6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)}, so f(6) = 2, \ f(11) = 3, \ f(16) = 1.
You are given a positive integer N. Determine whether there is a positive integer X less than or equal to N such that f(X) = 3, and if so, find the maximum such X.
There are T test cases to solve.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^{18}
Input
The input is given from Standard Input in the following format, where N_i represents the value of N in the i-th test case:
T N_1 N_2 \vdots N_T
Output
Print T lines.
The i-th line should contain the maximum positive integer X less than or equal to N_i such that f(X) = 3.
If there is no such positive integer X, print -1.
Sample Input 1
4 16 161 4 1000000000000000000
Sample Output 1
14 161 -1 936748722493063168
- For the first test case, f(14) = 3, \ f(15) = 4, \ f(16) = 1, so the maximum positive integer X satisfying X \leq 16 and f(X) = 3 is 14.
- For the second test case, f(161) = 3, so the maximum positive integer X satisfying X \leq 161 and f(X) = 3 is 161.
- For the third test case, f(1) = 1, \ f(2) = 1, \ f(3) = 2, \ f(4) = 1, so there is no positive integer X satisfying X \leq 4 and f(X) = 3.
- As seen in the fourth test case, the input and output values may not fit in a 32-bit integer type.