Problem:


Score : 600 points

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is A_i.
He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2.
Note that a ball cannot belong to multiple pairs.
Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls.
Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()

    #print(n)
    #print(nums)

    num_bin_digits = [1 << len("{:b}".format(x)) for x in nums]
    cnt = 0
    #print(num_bin_digits)

    for cur in reversed(range(n)):
        num = nums[cur]
        if not num:
            continue
        power_of_2 = num_bin_digits[cur]
        pair = power_of_2 - num

        idx = bisect.bisect_left(nums[:cur], pair)
        if idx == cur or nums[idx] != pair:
            continue

        nums[idx] = False
        cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(cnt, nums)

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()
    used = [False] * n

    num_bin_digits = [1 << len("{:b}".format(x)) for x in nums]
    cnt = 0

    for cur in reversed(range(n)):
        if used[cur]:
            continue

        num = nums[cur]
        power_of_2 = num_bin_digits[cur]
        pair = power_of_2 - num
        idx = -1
        if pair in nums[:cur]:
            idx = nums.index(pair)

        if idx != -1 and not used[idx]:
            used[idx] = True
            cnt += 1

        #print(idx, num, power_of_2, pair)
        #print(used)

    print(cnt)

    return

main()

Submission status: Wrong Answer

Solution code:
from math import *
 
n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    if(dict1[arr[i]]>0):
        val2=int(ceil(log(arr[i],2)))
        xd=2**val2
        if(xd-arr[i]!=arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
print(ans)

Submission status: Wrong Answer

Solution code:
from math import *
 
n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    if(dict1[arr[i]]>0):
        val2=int(ceil(log(arr[i],2)))
        xd=2**val2
        if(xd!=2*arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
    #print(dict1)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import *
 
n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=int(ceil(log(arr[i],2)))
    xd=2**val2
    if(xd!=2*arr[i]):
        try:
            if(dict1[xd-arr[i]]>0):
                ans+=1
                dict1[xd-arr[i]]-=1
                dict1[arr[i]]-=1
        except:
            KeyError
    else:
        if(dict1[arr[i]]>1):
            ans+=1
            dict1[arr[i]]-=2
    #print(dict1)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import *
 
n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1
#print(dict1)
ans=0
arr.sort(reverse=True)
for i in range(n):
    val2=int(ceil(log(arr[i],2)))
    xd=2**val2
    if(xd!=2*arr[i]):
        try:
            if(dict1[xd-arr[i]]>0):
                ans+=1
                dict1[xd-arr[i]]-=1
                dict1[arr[i]]-=1
                break
        except:
            KeyError
    else:
        if(dict1[arr[i]]>1):
            ans+=1
            dict1[arr[i]]-=2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import bisect

INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


def solve(num_cnt: list) -> int:
    if len(num_cnt) < 2:
        return 0
    num_cnt.sort()
    t = 2 ** (len(bin(num_cnt[-1])) - 2)
    used = [False] * len(num_cnt)
    cnt = 0
    for i in range(len(num_cnt))[::-1]:
        if used[i]:
            continue
        n = num_cnt[i]
        used[i] = True
        while 2 * n < t:
            t //= 2
        j = bisect.bisect_left(num_cnt, t - n)
        # print(n, t, j)
        if t - n == num_cnt[j] and n != t - n:
            cnt += 1
            used[j] = True

    return cnt


N = int(input())
A = inpl()

cnt_e, cnt_o = [], []
for a in A:
    if a % 2:
        cnt_o.append(a)
    else:
        cnt_e.append(a)

print(solve(cnt_e) + solve(cnt_o))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
u = [0 for i in range(len(a))]

b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

sum = 0
i = 0

#print(a)
while True:

    if u[i] > 0:
        i = i + 1
        if i >= len(a)-1:
            break        
        continue

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    
    if t > a[i]:
        i = i + 1
        if i >= len(a)-1:
            break
        continue

    first = i+1
    last = len(a)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t and u[midpoint] <= 0 :
            found = True
            sum += 1
            u[midpoint] += 1
        else:
            if t > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = sorted(list(map(int,input().split())))

count = 0

b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1

for i in range(len(a) - 1, -1, -1):
    if  b[a[i]] == 0:
        continue
    temp = a[i]
    b[a[i]] -= 1
    s=2**math.floor(math.log2(temp))
    st = 2*s - temp 
    if a ==[]:
        break
    if st in b and b[st] != 0:
        b[temp] -= 1
        b[2*s-temp] -= 1
        count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
bekijo = [2]

def is_bekijo(n):
    if n in bekijo:
        return True
    if n % 2 == 1:
        return False
    else:
        return is_bekijo(n / 2)

N = int(input())
A = list(map(int, input().split()))

A.sort()
#print(a)
A = A[::-1]
res = 0
for a in A:
    #print(a)
    for _a in A:
        if is_bekijo(a + _a):
            res += 1
            A.remove(a)
            A.remove(_a)
            break
            
print(res)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = sorted(list(map(int,input().split())))

count = 0



while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    b=2**math.floor(math.log2(temp))
    if a ==[]:
        break
    if 2*b-temp in a:
        count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = sorted(list(map(int,input().split())))

count = 0



while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

a.sort(reverse=True)

cntSet = 0
# cntList = [0 for _ in range(len(a))]
c = Counter(a)

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if a[i]==pair:
        cntSet += c[a[i]]//2
        c[a[i]] = c[a[i]] % 2
    elif c[pair]>0:
        c[a[i]] -= 1
        c[pair] -=1
        cntSet +=1
    # if pair in a and cntList[i]==0 and cntList[a.index(pair)]==0:
    #     cntList[i]=1
    #     cntList[a.index(pair)]=1
    #     cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = [int(i) for i in input().split()]

A.sort(reverse=True)
B = [2**math.ceil(math.log(i, 2)) - i for i in A]

c = 0
for i in B:
    if i in A:
        c += 1
        A.remove(i)
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

a.sort(reverse=True)

print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]
c = Counter(a)

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if pair in c.keys() and cntList[i]==0 and cntList[a.index(pair)]==0:
        cntList[i]=1
        cntList[a.index(pair)]=1
        cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = sorted(list(map(int,input().split())))

count = 0

b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1



while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    s=2**math.floor(math.log2(temp))
    if a ==[]:
        break
    if 2*s-temp in a and b[2*s-temp] > 0:
        count += 1
        b[temp] -= 1
        b[2*s-temp] -= 1
    
print(count)

Submission status: Wrong Answer

Solution code:
import math

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

    # return 2**math.ceil(math.log2(x))

a.sort(reverse=True)

print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
u = [0 for i in range(len(a))]

b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

sum = 0
i = 0

#print(a)
while True:

    if u[i] > 0:
        i = i + 1
        if i >= len(a)-1:
            break        
        continue

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    
    if t > a[i]:
        i = i + 1
        if i >= len(a)-1:
            break
        continue

    first = 0
    last = len(a)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if a[midpoint] == t and u[midpoint] <= 0 and midpoint != i:
            found = True
            sum += 1
            u[midpoint] += 1
        else:
            if t > a[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a,"b")))) - a
    if dic.get(a,0)>0:
        dic[a] -= 1
    if dic.get(small,0)>0:
        dic[small] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

    # return 2**math.ceil(math.log2(x))

a.sort(reverse=True)

# print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if pair in a and cntList[i]==0 and cntList[a.index(pair)]==0:
        # print(pair, cntList)
        cntList[i]=1
        # if cntList[a.index(pair)]==0:
        cntList[a.index(pair)]=1
        cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a+1,"b")))) - a
    if dic.get(a,0)>0:
        dic[a] -= 1
    if dic.get(small,0)>0:
        dic[small] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))

count = 0
a.sort()

while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    b=2**math.ceil(math.log2(temp))-temp
    if a ==[]:
        break
    if b in a:
        count += 1
        a.pop(a.index(b))
    
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a+1,"b")))) - a
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] -= 1
        dic[small] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    for d in As:
        n = (2 ** d.bit_length()) - d
        if d != n:
            if C[d] > 0 and C.get(n, 0) > 0:
                C[d] -= 1
                C[n] -= 1
                ans += 1
        else:
            ans += C[d]//2
            C[d] = 0
    return ans
 
 
if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(ans_solve(N, As))

Submission status: Wrong Answer

Solution code:
import math

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    # cnt = 0
    # while(x>1):
    #     x //=2
    #     cnt += 1
    # return 2**(cnt+1)

    return 2**math.ceil(math.log2(x))

a.sort(reverse=True)

# print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if pair in a and cntList[i]==0 and cntList[a.index(pair)]==0:
        # print(pair, cntList)
        cntList[i]=1
        # if cntList[a.index(pair)]==0:
        cntList[a.index(pair)]=1
        cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a,"b")))) - a
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] = dic.get(a)-1
        dic[small] = dic.get(small)-1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
print(dic)
ans = 0

for a in A:
    small = (1<<(len(format(a+1,"b")))) - a
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] = dic.get(a)-1
        dic[small] = dic.get(small)-1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    # cnt = 0
    # while(x>1):
    #     x //=2
    #     cnt += 1
    # return 2**(cnt+1)

    return 2**math.ceil(math.log2(x))

a.sort(reverse=True)

# print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if pair in a and cntList[i]==0:
        # print(pair, cntList)
        cntList[i]=1
        if cntList[a.index(pair)]==0:
            cntList[a.index(pair)]=1
            cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a,"b")))) - a
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] -= 1
        dic[small] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
u = [0 for i in range(len(a))]

def binarySearch(alist, item,exhi):
    first = 0
    last = len(alist)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item and u[midpoint] <= 0 and midpoint != exhi:
            found = True
            u[midpoint] += 1
        else:
            if item >= alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1

    return found


b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

sum = 0
i = 0

#print(a)
while True:

    if u[i] > 0:
        i = i + 1
        if i >= len(a)-1:
            break        
        continue

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    
    ret = binarySearch(a,t,i)
    if ret :
        sum += 1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
print(dic)
ans = 0

for a in A:
    if dic[a]==0:
        continue
    small = (1<<(len(format(a,"b")))) - a
    if dic.get(small,0)>0:
        dic[small] -= 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
u = [0 for i in range(len(a))]

def binarySearch(alist, item,exhi):
    first = 0
    last = len(alist)-1
    found = False

    while first<=last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item and u[midpoint] <= 0 and midpoint != exhi:
            found = True
            u[midpoint] += 1
        else:
            if item > alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1

    return found


b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

sum = 0
i = 0

#print(a)
while True:

    if u[i] > 0:
        i = i + 1
        if i >= len(a)-1:
            break        
        continue

    t = 0
    for bb in b :
        if bb > a[i]:
            t = bb - a[i]
            break
    
    ret = binarySearch(a,t,i)
    if ret :
        sum += 1
            
    i = i + 1
    if i >= len(a)-1:
        break

print(sum)

Submission status: Wrong Answer

Solution code:
n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

a.sort(reverse=True)

from collections import Counter
c = Counter(a)
print(c)

# print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if pair in a and cntList[i]==0:
        # print(pair, cntList)
        cntList[i]=1
        if cntList[a.index(pair)]==0:
            cntList[a.index(pair)]=1
            cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
lctr = sorted(list(ctr.items()),reverse=True)

ans = 0
for k,v in lctr:
    beki = 2**(len(bin(k))-2)
    a = beki-k
    if a == k:
        ans += v//2
    else:
        tmp = min(ctr[k], ctr[a])
        ans += tmp
        ctr[a] -= tmp
print(ans)

Submission status: Wrong Answer

Solution code:
n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

# a.sort(reverse=True)
a.sort()

from collections import Counter
c = Counter(a)
print(c)

# print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]

for i in range(len(a)-1, 0, -1):
    pair = nibeki(a[i])-a[i]
    if pair in a and cntList[i]==0:
        # print(pair, cntList)
        cntList[i]=1
        if cntList[a.index(pair)]==0:
            cntList[a.index(pair)]=1
            cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)

bb = 2
b = []
while bb <= 2000000000:
    bb *= 2
    b.append(bb)

ans = 0
while len(a) > 1:
    for i in range(1,len(a)):
        if a[0] + a[i] in b:
            ans += 1
            a.pop(0)
            a.pop(i-1)
            break
        
        if i == len(a)-1:
            a.pop(0)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
lctr = sorted(list(ctr.items()),reverse=True)

ans = 0
for k,v in lctr:
    beki = 2**(len(bin(k))-2)
    a = beki-k
    if a == k:
        ans += v//2
    else:
        tmp = min(v, ctr[a])
        ans += tmp
        ctr[a] -= tmp
print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1
pow2 = 1
while not pow2 > a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while not aa >= (pow2//2):
        pow2 //= 2
    v = aa
    rem = pow2 - aa
    if (not v in b) or (not rem in b):
        continue

    if rem != v:
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    else:
        hit = b[v] // 2
        cnt += int(hit)
        b[v] -= hit // 2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D.keys() :
        D[i] += 1
    else :
        D[i] = 1

ans = 0
A = sorted(A,reverse=True)
for i in A :
    r = 2**math.ceil(math.log2(i))
    if i == r :
        ans += D[i] // 2
    else :
        b = r-i
        if D[i] > 0 and D.get(b,0) > 0 :
            D[i] -= 1
            D[b] -= 1
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

a.sort(reverse=True)

# print(a)
cntSet = 0
cntList = [0 for _ in range(len(a))]

for i in range(len(a)):
    pair = nibeki(a[i])-a[i]
    if pair in a and cntList[i]==0:
        # print(pair, cntList)
        cntList[i]=1
        if cntList[a.index(pair)]==0:
            cntList[a.index(pair)]=1
            cntSet += 1

print(cntSet)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from math import log2, ceil

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
la = len(a)

ans = 0
while a:
    t = a.pop()
    la -= 1
    s = 2 ** ceil(log2(t)) - t
    j = bisect_left(a, s)
    if j >= la: continue
    if a[j] == s:
        a.remove(s)
        la -= 1
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1
pow2 = 1
while not pow2 > a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while not aa >= (pow2//2):
        pow2 //= 2
    v = aa
    rem = pow2 - aa
    if (not v in b) or (not rem in b):
        continue

    if rem != v:
        hit = min(b[v], b[rem])
        # print("hit:not: ", hit)
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    else:
        hit = b[v] // 2
        # print("hit: ", hit)
        # print(a)
        cnt += int(hit)
        # a[a.index(v)] = a[a.index(v)] % 2
        b[v] /= 2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2
#         d.append(c[n])
#     except:
#         pass
# d.sort(key=lambda x:len(x))
# d.reverse()

# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:
#             if p in j:
#                 try:
#                     d.pop(e+1)
#                 except:
#                     pass

# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1


# sum = 0
# for n in twopowerlist:
#     try:
#         sum += c[n]
#     except:
#         pass
# print("list: ", c)
# print(sum)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D :
        D[i] += 1
    else :
        D[i] = 1

ans = 0
A = sorted(A,reverse=True)
for i in A :
    r = 2**math.ceil(math.log2(i))
    if i == r :
        ans += D[i] // 2
    else :
        b = r-i
        if D[i] > 0 and D.get(b,0) > 0 :
            D[i] -= 1
            D[b] -= 1
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
a_odds = []
a_even = []

for i in range(N):
    if a[i]%2 != 0:
        a_odds.append(a[i])
    else:
        a_even.append(a[i])

a_odds.sort()
a_odds.reverse()
a_even.sort()
a_even.reverse()

count = 0

while(a_odds!=[]):
    temp = a_odds[0]
    a_odds.pop(0)
    b=2**math.floor(math.log2(temp))
    if a_odds ==[]:
        break
    if 2*b-temp in a_odds:
        count += 1
        a_odds.pop(a_odds.index(2*b-temp))
    
    
while(a_even!=[]):
    temp = a_even[0]
    a_even.pop(0)
    b=2**math.floor(math.log2(temp))
    if a_even ==[]:
        break
    if 2*b-temp in a_odds:
        count += 1
        a_even.pop(a_even.index(2*b-temp))

print(count)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()



c = [0] * n #使ったら1
res = 0

for i in range(n-1,-1,-1):
    if c[i] == 0:
        b = 1
        while b <= a[i]:
            b = b*2
        
        
        k = bisect.bisect_left(a,b-a[i])
        if i > k:
            if b - a[i] == a[k] and c[k] == 0:
                res += 1
                c[i] = 1
                c[k] = 1

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
aA = sorted([int(_) for _ in input().split()],reverse=True)
aA1 = [ _ for _ in aA if _ % 2 ]
aA0 = [ _ for _ in aA if _ % 2 == 0 ]


def searchPair(aD):
    iL = len(aD)
    dsT =set()
    iC = 0
    for i in range(iL):
        for j in range(i+1,iL):
            if i in dsT or j in dsT:
                break
            iWa =  aD[i] + aD[j]
            if not ( iWa & (iWa - 1)):
                dsT.add(i)
                dsT.add(j)
                iC += 1
                break

    return iC
iC = 0
iC += searchPair(aA1)
iC += searchPair(aA0)
print(iC)

Submission status: Wrong Answer

Solution code:
N = int(input())
AN=sorted(map(int,input().split()))[::-1]

C = 0
count = 0

D = []

for i in range(N):

    if i in D:
        continue

    A = int(AN[i])
    flag = False
    
    for j in range(i+1, len(AN)):

        B = int(AN[j])

        C = A + B
        
        while True:
            if C == 2:
                count += 1
                flag = True
                D.append(i)
                D.append(j)
                break

            mod = C % 2

            if mod == 0:
                C = C // 2
            else:
                break

        if flag:
            break

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = set(map(int, input().split()))

ans = 0
while a:
    t = max(a)
    a.discard(t)
    p = 1
    while True:
        if t < p <= 2 * t: break
        p *= 2
    s = p - t
    if s in a:
        a.discard(s)
        ans += 1

print(ans)