2013-02-13 20:02:44Morris
[UVA] 12571 - Brother & Sisters!
Brother & Sisters!
Taman is excited to announce that he has learnt bitwise AND operation. His Big Sister Titly
has given him a sequence of non-negative integers
x1, x2,..., xn as key. To test that whether
Taman knows bitwise AND operation or not, Taman is asked to find maximum value among
all (
a AND xi) where
1| Brother & Sisters! |
iN. But their youngest sister Tamanna is not happy with this. She
adds another condition that for a given sequence, Taman has to answer Q queries instead of
just one. Can you help poor Taman?
Note:
Expression
x AND y means applying the operation of bitwise AND to numbers x and y. This
operation exists in all modern programming languages, for example, in language C++ and
Java it is marked as "&".
Input
First line of input will contain the number of test cases, T5. Then T test cases follow.
First line of each test case contains two integers N (
1N100000) and Q (
1Q30000)
separated by a single space. Next line contains N integers
x1, x2,..., xn separated by a single
space (
0xi < 109). Each of next Q lines describes a query which consists of a single integer
a (
0a < 230).
Output
For each query output a single integer, the maximum value of ( a AND xi) where 1iN.
Sample Input
1 3 3 1 2 3 10 11 12
Sample Output
2 3 0
Problem Setter: Muhammed Hedayet
Alternate Solution: Kazi Rakibul Hossain
a < 230 是個關鍵，把 255 以下的值都找出來。
#include <stdio.h>
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int t, n, q, i, x, a;
ReadInt(&t);
//scanf("%d", &t);
while(t--) {
ReadInt(&n), ReadInt(&q);
// scanf("%d %d", &n, &q);
int m[256] = {};
while(n--) {
ReadInt(&x);
//scanf("%d", &x);
m[x&0xff] = 1;
}
while(q--) {
ReadInt(&a);
//scanf("%d", &a);
x = 0;
for(i = 255; i > x; i--)
if(m[i] && (a&i) > x)
x = a&i;
printf("%d\n", x);
}
}
return 0;
}