Codeforces Round #276 (Div. 2)

Codeforces Round #276 (Div. 2)

C. 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).<†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkVhY2ggb2YgdGhlIGZvbGxvd2luZyA8ZW0+bjwvZW0+IGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzIDxlbT5sPC9lbT48ZW0+aTwvZW0+LD88ZW0+cjwvZW0+PGVtPmk8L2VtPiChqgogdGhlIGFyZ3VtZW50cyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgcXVlcnkgKDA/odw/PGVtPmw8L2VtPjxlbT5pPC9lbT4/odw/PGVtPnI8L2VtPjxlbT5pPC9lbT4/odw/MTAxOCkuPC9wPgoKCgpPdXRwdXQKPHA+CkZvciBlYWNoIHF1ZXJ5IHByaW50IHRoZSBhbnN3ZXIgaW4gYSBzZXBhcmF0ZSBsaW5lLjwvcD4KCgoKU2FtcGxlIHRlc3QocykKCgoKaW5wdXQKPHByZSBjbGFzcz0="brush:java;">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

¿´ÁËÎҵĴúÂ룬×Ô¼º¶ÔÕÕÄ£ÄâϾÍÖªµÀ˼·ÁË£º

#include 
#include 
#include 
#include 
using namespace std;


__int64  bit[65];




int main() {

   bit[0]=1;
    for(int i = 1; i <= 63; i++) {
        bit[i] = 2*bit[i-1];
    }


    int n;
    scanf("%d",&n);
    while(n--) {
         __int64 l,r;
         scanf("%I64d%I64d",&l,&r);
         int j;
         __int64 sum = 0;
         for(j = 0; sum <=r; j++)
         {
             sum += bit[j];
         }

         j--;

         while(sum > r)
         {
             sum -= bit[j];
             if(sum < l) sum += bit[j];
             j--;
         }

        printf("%I64d\n",sum);
    }
    return 0;
}