[UVA][Greedy] 10718 - Bit Mask＠Morris' Blog｜PChome Online 個人新聞台

2012-05-30 07:03:07| 人氣2,750| 回應2 | 上一篇 | 下一篇

[UVA][Greedy] 10718 - Bit Mask

推薦 0 收藏 0 轉貼0 訂閱站台

          Problem A
      Bit Mask
    
      Time Limit
      1 Second
    
In bit-wise expression, mask is a common term. You can get a certain bit-pattern using mask. For example, if you want to make first 4 bits of a 32-bit number zero, you can use 0xFFFFFFF0 as mask and perform a bit-wise AND operation. Here you have to find such a bit-mask.
Consider you are given a 32-bit unsigned integer N. You have to find a mask M such that L ≤ M ≤ U and N OR M is maximum. For example, if N is 100 and L = 50, U = 60 then M will be 59 and N OR M will be 127 which is maximum. If several value of M satisfies the same criteria then you have to print the minimum value of M.
Input
  Each input starts with 3 unsigned integers N, L, U where L ≤ U. Input is terminated by EOF.
Output
  For each input, print in a line the minimum value of M, which makes N OR M maximum.
Look, a brute force solution may not end within the time limit.
          Sample Input
      Output for Sample Input
    
      100 50 60
      100 50 50
      100 0 100
      1 0 100
      15 1 15
      59
      50
      27
      100
      1
    

  如果原本那個 bit 為 1, 選擇與否取決於有沒有大於低限
原本那個 bit 為 0, 選擇與否取決於有沒有小於上限

#include <stdio.h>

int main() {
    long long N, L, R, ans, l, r;
    while(scanf("%lld %lld %lld", &N, &L, &R) == 3) {
        ans = 0;
        long long i;
        for(i = 31; i >= 0; i--) {
            if(N&(1LL<<i)) {
                r = ans + (1LL<<i);
                if(r <= L)
                    ans += 1LL<<i;
            } else {
                l = ans + (1LL<<i);
                if(l <= R)
                    ans += 1LL<<i;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}