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:
def invbisect(a,x):
    right = len(a)-1
    left = 0
    while abs(left-right) > 1:
        if a[(left+right)//2] <= x:
            right = (left+right)//2
        else:
            left = (left+right)//2
    return right

n = int(input())
a = list(map(int,input().split()))
two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1
two.reverse()
m = len(two)

a.sort()
a.reverse()
counter = 0

i = 0
while i < n-1:
    for k in range(m):
        if two[k] > a[i]:
            ind = invbisect(a,two[k]-a[i])
            if a[ind] == two[k]-a[i]:
                a.pop(ind)
                a.pop(i)
                i -= 1
                n -= 2
                counter += 1
    i += 1
print(counter)

Submission status: Wrong Answer

Solution code:
def invbisect(a,x):
    right = len(a)-1
    left = 0
    while abs(left-right) > 1:
        if a[(left+right)//2] <= x:
            right = (left+right)//2
        else:
            left = (left+right)//2
    return right

n = int(input())
a = list(map(int,input().split()))
two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1
two.reverse()
m = len(two)

a.sort()
a.reverse()
print(a)
print(invbisect(a,5))
counter = 0

i = 0
while i < n-1:
    for k in range(m):
        if two[k] > a[i]:
            ind = invbisect(a,two[k]-a[i])
            if a[ind] == two[k]-a[i]:
                a.pop(ind)
                a.pop(i)
                i -= 1
                n -= 2
                counter += 1
    i += 1
print(counter)

Submission status: Wrong Answer

Solution code:
# _*_ coding:utf-8 _*_
#  Atcoder_Grand_Contest029-B
#  https://agc029.contest.atcoder.jp/tasks/agc029_b
from collections import Counter

def  maxCountPair(n_ballCount,a_ballDatas):
	a_ballDatas.sort(reverse=True)
	ballDictBox = Counter(a_ballDatas)
	ballCountRange = range(0,n_ballCount)
	pairCount = 0
	for i in ballCountRange:
		getBallNumber = a_ballDatas[i]
		getBallNumberBin = getBallNumber.bit_length()
		nextTwoPower = 2**getBallNumberBin
		diffNumber = nextTwoPower - getBallNumber
		if 1 <= ballDictBox[diffNumber] :
			if getBallNumber != diffNumber:
				pairCount = pairCount + 1
				ballDictBox[getBallNumber]=ballDictBox[getBallNumber]-1
				ballDictBox[diffNumber] = ballDictBox[diffNumber]-1
			else:
				if 2 <= ballDictBox[diffNumber]:
					pairCount = pairCount + 1
					ballDictBox[diffNumber]=ballDictBox[diffNumber]-2
	answer = pairCount
	return answer


if __name__ == '__main__':
	n_ballCount=int(input())
	a_ballDatas=list((map(int,input().split(" "))))
	solution=maxCountPair(n_ballCount,a_ballDatas)
	print(solution)

Submission status: Wrong Answer

Solution code:
# _*_ coding:utf-8 _*_
#  Atcoder_Grand_Contest029-B
#  https://agc029.contest.atcoder.jp/tasks/agc029_b
from collections import Counter

def  maxCountPair(n_ballCount,a_ballDatas):
	a_ballDatas.sort(reverse=True)
	ballDictBox = Counter(a_ballDatas)
	ballCountRange = range(0,n_ballCount)
	pairCount = 0
	for i in ballCountRange:
		getBallNumber = a_ballDatas[i]
		getBallNumberBin = getBallNumber.bit_length()
		nextTwoPower = pow(2,getBallNumberBin)
		diffNumber = nextTwoPower - getBallNumber
		if 1 <= ballDictBox[diffNumber] :
			if getBallNumber != diffNumber:
				pairCount = pairCount + 1
				ballDictBox[getBallNumber]=ballDictBox[getBallNumber]-1
				ballDictBox[diffNumber] = ballDictBox[diffNumber]-1
			else:
				if 2 <= ballDictBox[diffNumber]:
					pairCount = pairCount + 1
					ballDictBox[diffNumber]=ballDictBox[diffNumber]-2
	answer = pairCount
	return answer


if __name__ == '__main__':
	n_ballCount=int(input())
	a_ballDatas=list((map(int,input().split(" "))))
	solution=maxCountPair(n_ballCount,a_ballDatas)
	print(solution)

Submission status: Wrong Answer

Solution code:
import bisect

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

beki = [2]
while beki[-1]*2 <= A[-1]+A[-2]:
    beki.append(beki[-1]*2)

ans = 0
ind = 0
for b in beki[::-1]:
    ind = 0
    ind_max = len(A)
    while ind < len(A) and len(A) > 0:
        tar = b - A[ind]
        if tar < 0:
            break
        else:
            ind1 = ind
            ind2 = bisect.bisect_left(A,tar,ind1,len(A))

            if ind2 < len(A):

                dam = A.pop(ind1)
                dam = A.pop(ind2-1)
                ans += 1

            else:
                ind += 1

        if len(A) <= 1:
            break
    if len(A) <= 1:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

n = int(input())
a_list = list(map(int, input().split()))
d = defaultdict(int)
a_list.sort()

for a in a_list:
  d[a] += 1

a_list = sorted(list(set(a_list)))
c = 0
for a in a_list:
  m = int(math.log(a, 2))
  x = 2 ** (m+1) - a
  if x == a:
    c += d[a] // 2
    d[a] -= d[a] // 2
  else:
    c += min(d[x], d[a])
    d[x] -= min(d[x], d[a])

print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def log2(n):
  if n < 2:
    return 0
  else:
    return 1 + log2(n // 2)

n = int(input())
a_list = list(map(int, input().split()))
d = defaultdict(int)
a_list.sort()

for a in a_list:
  d[a] += 1

a_list = list(set(a_list))
c = 0
for a in a_list:
  m = log2(a)
  x = 2 ** (m+1) - a
  if x == a:
    c += d[a] // 2
    d[a] -= d[a] // 2
  else:
    c += min(d[x], d[a])
    d[x] -= min(d[x], d[a])

print(c)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

n = int(input())
a_list = list(map(int, input().split()))
d = defaultdict(int)
a_list.sort()

for a in a_list:
  d[a] += 1

a_list = list(set(a_list))
c = 0
for a in a_list:
  m = int(math.log(a, 2))
  x = 2 ** (m+1) - a
  if x == a:
    c += d[a] // 2
    d[a] -= d[a] // 2
  else:
    c += min(d[x], d[a])
    d[x] -= min(d[x], d[a])

print(c)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = list(map(int,input().split()))
two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1
two.reverse()
m = len(two)
a.sort()
i = 0
counter = 0
while i <= n-1:
    for k in range(m):
        if two[k] > a[i]:
            ind = bisect.bisect_left(a,two[k]-a[i])
            if ind <= n-1 and a[ind] == two[k]-a[i] and ind != i:
                counter += 1
                if ind > i:
                    a.pop(ind)
                    a.pop(i)
                else:
                    a.pop(i)
                    a.pop(ind)
                n += -2
                i -= 1
    i += 1
print(counter)

Submission status: Wrong Answer

Solution code:
N=int(input())
buf=[]
buf=input().split()
A=[]
flug=[]
for i in range(N):
    A.append(int(buf[i]))
    flug.append(0)
A.sort()
c=0
index=[i for i in reversed(range(0,32))]
loop=[i for i in range(N-2)]
for i in index:
    sum=1<<i
    left=0
    right=N-1
    for j in loop:
        if left<right:
            if flug[left]==1:
                left=left+1
            elif flug[right]==1:
                right=right-1
            elif (A[left]+A[right])==sum:
                flug[left]=1
                flug[right]=1
                left=left+1
                right=right-1
                c=c+1
            elif(A[left]+A[right])>sum:
                right=right-1
            else:
                left=left+1
print(c)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
N = int(input())
A = sorted(int(i) for i in input().split())

d = defaultdict(lambda: 0)
for i in A:
    d[i] += 1

c = 0
for k, v in sorted(d.items(), reverse=True):
    l = 2**int(math.log(k, 2) + 1) - k
    if k == l:
        c += v // 2
    elif l in d:
        w = d[l]
        if v > w:
            c += w
            d[l] = 0
        else:
            c += v
            d[l] = v-w
print(c)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
N = int(input())
A = sorted(int(i) for i in input().split())

d = defaultdict(lambda: 0)
for i in A:
    d[i] += 1

c = 0
for k, v in sorted(d.items(), reverse=True):
    d[k] = 0
    l = 2**int(math.log(k, 2) + 1) - k
    if l in d:
        w = d[l]
        if v > w:
            c += w
            d[l] = 0
        else:
            c += v
            d[l] = v-w
print(c)

Submission status: Wrong Answer

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

c = 0
while A:
    k = 2**int(math.log(A[-1], 2) + 1)
    v = A.pop()
    while k > 2*v:
        k //= 2
    w = k - v
    if w in A:
        c += 1
        A.remove(w)
print(c)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = sorted((int(i) for i in input().split()), reverse=True)

c = 0
for i, v in enumerate(A[:-1]):
    w = 2**int(math.log(v, 2) + 1) - v
    if w in A[i+1:]:
        c += 1
        A.remove(w)
print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [1, 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]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1
    else:
        items[a] = 1
A_list.sort(reverse=True)
two_list
import bisect
for a in A_list:
    if items[a] >= 1:
        index = bisect.bisect_left(two_list, a)
        for t in two_list[index:]:
            m = t - a
            if m in items.keys():
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 2
                    break

                elif m != a and items[m] >= 1 and items[a] >= 1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

Submission status: Wrong Answer

Solution code:
input()
A=list(map(int,input().split()))
def add(i):
    global n
    #print("i=",i)
    if i in b:
        if b.get(i,0) == m:
            b[i]=0
            add(i-1)
        else:
            b[i]=b.get(i,b[i])+1
            n=max(n,b[i])
    else:
        b[i]=b.get(i,b[1])+1
        n=max(n,b[i])

lo=1
hi=10**6
while lo < hi:
    m = (lo + hi)//2 
    ba=0
    b={}
    b[0]=0
    b[1]=1
    n=1
    for fr in A:
        #print(b,m,ba,fr)
        if fr == ba:
            add(fr)
        if fr < ba:
            c={}
            for bb in list(b.keys()):
                if bb <= fr:
                    c[bb]=b[bb]
            b=c
            add(fr)
        if b[0] >= 1:
            lo = m+1
            flag=0
            break
        ba=fr
    #print(b)
    hi=min(n,m)
    lo=1
print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [1, 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]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1
    else:
        items[a] = 1
A_list.sort(reverse=True)
two_list

for a in A_list:
    if items[a] >= 1:
        for t in two_list:
            m = t - a
            if m in items.keys():
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 2
                    break

                elif m != a and items[m] >= 1 and items[a] >= 1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [1, 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]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1
    else:
        items[a] = 1
A_list.sort(reverse=True)
two_list.reverse()

for a in A_list:
    if items[a] >= 1:
        for t in two_list:
            m = t - a
            if m in items.keys():
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break

                elif m != a and items[m] >= 1 and items[a] >= 1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

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**int(math.log(i, 2)+1) - i for i in A]

c = 0
for i, v in enumerate(B[:-1]):
    if v in A[i+1:]:
        c += 1
        A.remove(v)
print(c)

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**int(math.log(i, 2)+1) - i for i in A]

c = 0
for i, v in enumerate(B[:-1]):
    if v in A[i+1:]:
        c += 1
        A[A[i+1:].index(v)] = 0
print(c)

Submission status: Wrong Answer

Solution code:
g=[]
def judge(x):
    if x in g:
        return 1
    a=x
    while(x>1):
        if x%2 != 0:
            return 0
        x/=2
    g.append(a)
    return 1

N=int(input())
buf=[]
buf=input().split()
A=[]
for i in range(N):
    A.append(int(buf[i]))
A.sort()
A.reverse()
c=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[j]!=-1:
            if judge(A[i]+A[j])==1:
                A[j]=-1
                c=c+1
                break
print(c)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
start=0
x.sort()
for i in range(len(x))[::-1]:
    for j in range(len(t)):
        if t[j] < x[i]:
            break
        if t[j]-x[i] in c.keys():
            if t[j]-x[i] == x[i] and c[x[i]] >= 2:
                c[x[i]] -= 2
                count +=1
            elif c[t[j]-x[i]]>0 and c[x[i]]>0:
                c[t[j]-x[i]] -= 1
                c[x[i]] -= 1
                count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
#print(c)
#print("x=",x)
#print("t=",t)
for i in range(len(x))[::-1]:
    if x[i] != 0:
        for j in range(len(t)):
            if t[j] <= x[i]:
                break
            if t[j]-x[i] in c:
                if t[j]-x[i] == x[i]:
                    if c.get(x[i],-1) >= 2:
                        c[x[i]] -= 2
                        count +=1
                        break
                else:
                    if c.get(t[j]-x[i],-1)>0 and c.get(x[i],-1)>0:
                        c[t[j]-x[i]] -= 1
                        c[x[i]] -= 1
                        count+=1
                        break
#print(c)    
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
start=0
#print(c)
#print("x=",x)
#print("t=",t)
for i in range(len(x))[::-1]:
    #print(c)
    if x[i] != 0:
        #print("X=",x[i])
        for j in range(start,len(t)):
            #print(j)
            if t[j] > 2*x[i]:
                start=j
            if t[j] <= x[i]:
                break
            elif t[j]-x[i] in c:
                if t[j]-x[i] == x[i]:
                    if c.get(x[i],-1) >= 2:
                        c[x[i]] -= 2
                        count +=1
                        break
                else:
                    if c.get(t[j]-x[i],-1)>0 and c.get(x[i],-1)>0:
                        c[t[j]-x[i]] -= 1
                        c[x[i]] -= 1
                        count+=1
                        break
#print(c)    
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
x=list(map(int,input().split()))
x.sort()
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
c={}
count=0
start=0
#print("x=",x)
#print("t=",t)
for i in range(len(x))[::-1]:
    #print(c)
    if x[i] != 0:
        #print("X=",x[i])
        for j in range(start,len(t)):
            #print(j)
            if t[j] > 2*x[i]:
                start=j
            if t[j] <= x[i]:
                break
            if t[j]-x[i] != 0:
                #print(t[j]-x[i],"A")
                if t[j]-x[i] in x:
                    #print("B")
                    p=bisect.bisect_left(x,t[j]-x[i],0,i)
                    if c.get(p,1) == 1 and c.get(i,1) == 1 and p != i:
                        c[i] = 0
                        c[p] = 0
                        count+=1
                        break
#print(c)
print(count)

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())
A = [int(i) for i in input().split()]

ans = 0
A = sorted(A, reverse=True)
A2 = copy.deepcopy(A)

print(A)

for i in range(len(A)):
    for j in reversed(range(i+1, (len(A2)))):
        num = A[i] + A2[j]
        if not (num & (num - 1)):
            ans += 1
            del A2[j]
            print(i,j)
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())
A = [int(i) for i in input().split()]

ans = 0
even = []
odd = []

for i in range(N):
    if A[i] % 2 == 0:
        even.append(A[i])
    else:
        odd.append(A[i])

even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)

even2 = copy.deepcopy(even)
odd2 = copy.deepcopy(odd)

for i in range(len(even)):
    for j in reversed(range((len(even2)))):
        if i >= j:
            break
        num = even[i] + even2[j]
        if not (num & (num - 1)):
            ans += 1
            del even2[j]
            break


for i in range(len(odd)):
    for j in reversed(range((len(odd2)))):
        if i >= j:
            break
        num = odd[i] + odd2[j]
        if not (num & (num - 1)):
            ans += 1
            del odd2[j]
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(36)])
ans = 0
for pow2 in pow2_set:
    print(pow2)
    l,r = 0,N-1
    while l < r:
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r -= 1
        else:
            r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(25)])
ans = 0
for pow2 in pow2_set:
    l,r = 0,N-1
    while l < r:
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r -= 1
        else:
            r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
ans = 0
s = set([ 1<<i for i in range(25)])

for i in range(N-1,0,-1):
    if used[i] == 1:
        continue
    used[i] = 1
    for j in range(i-1,-1,-1):
        if used[j] == 0 and (i+j) in s:
            used[j] = 1
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
ans = 0
for i in range(N):
    if used[N-i-1] == 1:
        continue
    used[N-i-1] = 1
    it = 2
    mx = 2 * A[N-i-1]
    while it <= mx:
        it <<= 1
    while it != 1:
        target = (it - A[N-i-1])
        ng,ok = -1 , N-1
        while abs(ok - ng) > 1:
            mid = (ok+ng) // 2
            if A[mid] < target or (target == A[mid] and used[mid] == 1):
                ng = mid
            else:
                ok = mid
        if target == A[ok] and used[ok] == 0:
            ans += 1
            used[ok] = 1
            break

        it >>= 1


print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
ans = 0
for i in range(N):
    if used[N-i-1] == 1:
        continue
    used[N-i-1] = 1
    it = 2
    while it < 2*A[N-i-1]:
        it <<= 1
    while it != 1:
        target = (it - A[N-i-1])
        ng,ok = -1 , N-1
        while abs(ok - ng) > 1:
            mid = (ok+ng) // 2
            if A[mid] < target or (target == A[mid] and used[mid] == 1):
                ng = mid
            else:
                ok = mid

        if target == A[ok] and used[ok] == 0:
            ans += 1
            used[ok] = 1
            break

        it >>= 1


print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
N = int(input())
A = inpl()
A.sort(reverse = True)
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: 0)
    ml = bisect.bisect_left(A, k)
    for i in A[:ml]:
        if H[k-i] > 0:
            H[k-i] -= 1
            ans += 1
        else:
            H[i] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
N = int(input())
A = inpl()
A.sort(reverse = True)
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: 0)
    ml = bisect.bisect_left(A, k)
    for i in A[:ml]:
        if H[k-i]:
            H[k-i] -= 1
            ans += 1
        else:
            H[i] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()
def pair(x):
    k = 1 
    while (x - k > 0): 
        k = k*2 
    return k - x 
ret = 0 
taken = []
for i in range(len(a)):
    if not(i in taken):
        try:
            pi = a.index(pair(a[i]))
            ret += 1
            taken.append(pi)
        except ValueError:
            pass
print(ret)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c=collections.Counter(A)

pairCounter=0

beki=7
nibeki=2**beki

for i in range(N):
  target = A[i]
  if c[target] < 1:
    continue
  c[target]-= 1

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in c.keys() and c[pair] > 0:
    c[pair]-= 1
    pairCounter+=1

print(pairCounter)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c=collections.Counter(A)

pairCounter=0

beki=7
nibeki=2**beki

for i in range(N):
  target = A[i]
  if c[target] < 0:
    continue
  c[target]-= 1

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in c.keys() and c[pair] > 0:
    c[pair]-= 1
    pairCounter+=1

print(pairCounter)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c=collections.Counter(A)

pairCounter=0

beki=7
nibeki=2**beki

for i in range(N):
  target = A[i]
  if c[target] < 0:
    continue
  c[target]= -1

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in c.keys():
    c[pair]= -1
    pairCounter+=1

print(pairCounter)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=sorted((map(int, input().split())), reverse=True)
a2=Counter(a)
c=0
for i in a:
    a2[i]-=1
    n=i^2**i.bit_length()-1
    if a2[n+1]>0:
        a2[n+1]-=1
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0

beki=7
nibeki=2**beki

for i in range(N):
  target = A[i]
  if target < 0:
    continue
  A[i] = -1  

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  #if pair in A:
  #  A[A.index(pair)] = -1
  #  pairCounter+=1

print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0

beki=7
nibeki=2**beki

for i in range(N):
  target = A[i]
  if target < 0:
    continue
  A[i] = -1  

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in A:
    #A[A.index(pair)] = -1
    pairCounter+=1

print(pairCounter)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0

beki=7
nibeki=2**beki

for i in range(N):
  target = A[i]
  if target < 0:
    continue
  A[i] = -1  

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in A:
    A[A.index(pair)] = -1
    pairCounter+=1

print(pairCounter)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
a2=Counter(a)
c=0
for i in a:
    a2[i]-=1
    n=i^2**(len(bin(i))-2)-1
    if a2[n+1]>0:
        a2[n+1]-=1
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
a2=Counter(a)
c=0
for i in a:
    n=i^2**(len(bin(i))-2)-1
    if a2[n+1]:
        a2[n+1]-=1
        a2[i]-=1
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  target = A[i]
  A[i] = -1
  if target < 0:
    continue
  for b in range(9):
    beki=2**b
    if beki > target:
      pair= beki - target
      if pair in A:
        A[A.index(pair)] = -1
        pairCounter+=1
      break
print(pairCounter)
#print(2)

Submission status: Wrong Answer

Solution code:
import itertools
import math
a = [(i, int(v)) for i, v in enumerate(input().split())]
b = list(itertools.combinations(a,2))
c = []
h = []
for i, v in enumerate(b):
    if math.log2(b[i][0][1] + b[i][1][1]) % 1 == 0:
        c.append(b[i])
import copy
if len(c) <= 1:
    h.append(len(c))
elif len(c) >= 2:
    for i in range(len(c)):
        d = copy.deepcopy(c)
        d.remove(c[i])
        count = 0
        for v in range(len(c) - 1):
            e = (c[i][0][0] != d[v][0][0])
            f = (c[i][1][0] != d[v][1][0])
            if(e == True and f == True):
                count += 1
        h.append(count + 1)
print(max(h) if max(h) <= int(math.floor(len(a) / 2)) else math.floor(len(a) / 2))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    beki=2**b
    if beki > A[i]:
      pair= beki - A[i]
      if pair in A:
        A[A.index(pair)] = -1
        pairCounter+=1
      A[i] = -1
      break
print(pairCounter)
#print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    beki=2**b
    if beki > A[i]:
      pair= beki - A[i]
      if pair in A:
        A[A.index(pair)] = -1
        pairCounter+=1
      A[i] = -1
      break
#print(pairCounter)
print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    beki=2**b
    if beki > A[i]:
      pair= beki - A[i]
      if A.count(pair) >0:
        #A[A.index(pair)] = -1
        pairCounter+=1
      A[i] = -1
      break
#print(pairCounter)
print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    beki=2**b
    if beki > A[i]:
      pair= beki - A[i]
      """
      if A.count(pair) >0:
        A[A.index(pair)] = -1
        pairCounter+=1
      """
      A[i] = -1
      break
#print(pairCounter)
print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy

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

pairCounter=0
for i in range(N):
  if A[i] < 0:
    continue
  for b in range(9):
    beki=2**b
    if beki > A[i]:
      pair= beki - A[i]
      if A.count(pair) >0:
        A[A.index(pair)] = -1
        pairCounter+=1
      A[i] = -1
      break
print(pairCounter)

Submission status: Wrong Answer

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

A.sort()
#print(a)
A = A[::-1]
res = 0
while len(A) >= 2:
    n = 2 ** A[0].bit_length() - A[0]
    if n in A:
        res += 1
        A.pop(A.index(n))
    A.pop(0)
            
print(res)

Submission status: Wrong Answer

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

A.sort()
#print(a)
A = A[::-1]
res = 0
while len(A) >= 2:
    for i in range(1, 33):
        n = 2 ** i - A[0]
        #print(n)
        if n in A:
            res += 1
            A.pop(A.index(n))
            break
    A.pop(0)
            
print(res)