Codeforces Round 796 (div 2)

[li-xin-yi]

https://codeforces.com/contest/1688

[li-xin-yi]

Problem A: Cirno's Perfect Bitmasks Classroom

Because x AND y > 0, both of them must have a common 1-bit. First find that lowest 1 and then check how to make x XOR y>0.

def solve(x):
    n = x.bit_length()
    one = n+1
    for i in range(n+1):
        if x & (1<<i):
            one = i
            break
    if (1<<one)^x: return 1<<one
    for i in range(n+1):
        if i == one:
            continue
        temp = (1<<one) + (1<<i)
        if temp^x: return temp
    return (1<<one) + (1<<n)

T = int(input())

for _ in range(T):
    x = int(input())
    print(solve(x))

[li-xin-yi]

Problem B: Patchouli's Magical Talisman

If there exists one odd number in the A, we can add other even numbers to the odd number once to cancel out those even numbers. After we have at least one odd number in A, any even number can be removed by only one step.

First, calculate how many times are needed to reduce A[i] to an odd value by only reduction (//2), we denote the times as times(x), then find if any times(x)=0, if there is, only need to add those even numbers to the odd number. Otherwise, find out the min times(x) and first reduce that x to an odd, then add other n-1 evens one by one.

def times(x):
    res = 0
    while x%2 == 0:
        x //= 2
        res += 1
    return res

def solve(A,n):
    odds = [times(x) for x in A]
    min_val = min(odds)
    if min_val == 0:
        return len([x for x in odds if x>0])
    else:
        return min_val + n - 1 

T = int(input())
for _ in range(T):
    n = int(input())
    lst = list(map(int, input().split()))
    print(solve(lst,n))