CodeForces 484A Bits(水题)

A. Bits

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's denote as  the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).

Each of the following n lines contain two integers li, ri — the arguments for the corresponding query (0 ≤ li ≤ ri ≤ 1018).

Output

For each query print the answer in a separate line.

Sample test(s)

input

3
1 2
2 4
1 10

output

1
3
7

Note

The binary representations of numbers from 1 to 10 are listed below:

110 = 12

210 = 102

310 = 112

410 = 1002

510 = 1012

610 = 1102

710 = 1112

810 = 10002

910 = 10012

1010 = 10102

题意：给定l和r，找一个数x，满足 l<=x<=r，且x的二进制形式中1的数量要最多

思路：模拟一下，从高位到地位扫，如果r[p]==l[p]，那么答案的p位就和他们一样，否则必有r[p]=1 && l[p]=0，那就让答案p位为0，后面其余位为1

擦。。过了pretest没过final test，原因是我数组忘记初始化了，好粗心。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-6;
const int N = 100;
int cas = 1;

bool a[N],b[N],c[N];
int mx;

void ltob(ll x,bool *arr)
{
    int sz=0;
    while(x)
        arr[sz++]=x&1,x>>=1;
    if(mx<sz) mx=sz;
}

bool judge(int p)
{
    for(;p>=0;p--)
        if(a[p]==0) return 0;
    return 1;
}

void work(int p)
{
    if(p<0) return;
    if(judge(p))
        for(int i=p;i>=0;i--)   c[i]=1;
    else{
        if(a[p] == b[p]) c[p]=a[p],work(p-1);
        else{
            for(int i=p-1;i>=0;i--)
                c[i]=1;
        }
    }
}

void run()
{
    ll l,r;
    scanf("%I64d%I64d",&l,&r);
    if(l==r) cout<<l<<endl;
    else{
        mx=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        ltob(r,a);
        ltob(l,b);

//        cout<<"a:";for(int i=mx-1;i>=0;i--) printf("%d",a[i]); puts("");
//        cout<<"b:";for(int i=mx-1;i>=0;i--) printf("%d",b[i]); puts("");
        memset(c,0,sizeof(c));
        work(mx-1);
//        cout<<"c:";for(int i=mx-1;i>=0;i--) printf("%d",c[i]); puts("");
        ll ans = 0, base = 1;
        for(int i=0;i<mx;i++){
            if(c[i]) ans+=base;
            base<<=1;
        }
        cout<<ans<<endl;
    }
}

int main()
{
    #ifdef LOCAL
//    freopen("case.txt","r",stdin);
    #endif
    int _;
    scanf("%d",&_);
    while(_--)
        run();
    return 0;
}