UESTC 491 Tricks in Bits

​​Tricks in Bits​​

​​Submit​​​ ​​Status​​

Description

Given 

N unsigned 

64-bit

integers, you can ​​bitwise NOT​​​ each or not. Then you need to add operations selected from ​​bitwise XOR​​​, ​​bitwise OR​​​and ​​bitwise AND​​, between any two successive integers and calculate the result. Your job is to

make the result as small as possible.

Input

The first line of the input is 

T (no more than 

1000), which stands for the number of test cases you need to solve.Then 

T blocks follow. The first line of each block contains a single number 

N (

1≤N≤100) indicating the number of unsigned 

64-bit integers. Then 

n

Output

For every test case, you should output ​​Case #k:​​ first, where 

k indicates the case number and counts from 

1. Then output the answer.

Sample Input

2 
3 
1 2 3 
2 
3 6

Sample Output

Case #1: 0 

Case #2: 1

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
typedef unsigned long long int LL;
int n;
LL ans;
LL MAX;
LL a[105];
LL min(LL a,LL b){return (a<b?a:b);}
void dfs(LL num,int cnt)
{
    if(ans==0)
        return;
    if(num==0)
    {
        ans=0;
        return;
    }
    if(cnt==n+1)
    {
        ans=min(ans,num);
        return;
    }
    dfs(num|(~a[cnt]),cnt+1);
    dfs(num&(~a[cnt]),cnt+1);
    dfs(num^(~a[cnt]),cnt+1);
    dfs(num|a[cnt],cnt+1);
    dfs(num&a[cnt],cnt+1);
    dfs(num^a[cnt],cnt+1);
}
int main()
{
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%llu",&a[i]);
        MAX=1;
        MAX<<=63;
        ans=MAX;
        dfs(a[1],2);
        dfs(~a[1],2);
        printf("Case #%d: %llu\n",++cas,ans);
    }
    return 0;
}