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: Accepted

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
A.append(999999999999999)
B=[]
for i in range(1,35):
    B.append(2**i)
ans=0
for i in range(N):
    if A[N-1-i]==int(A[N-1-i]):
        for j in range(len(B)):
            if A[N-1-i]<B[j]:
                break
        if A[bisect.bisect_left(A,B[j]-A[N-1-i])]==B[j]-A[N-1-i]:
            if bisect.bisect_left(A,B[j]-A[N-1-i])<N-1-i:
                A[bisect.bisect_left(A,B[j]-A[N-1-i])]-=0.1
                A[N-1-i]+=0.1
                ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
input()
A=list(map(int,input().split()))
A.sort(reverse=True)
C=Counter(A)
ans=0
for a in A:
    if not C[a]:
        continue
    C[a]-=1
    t=2**a.bit_length()-a
    if C[t]:
        C[t]-=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
input()
A=list(map(int,input().split()))
A.sort(reverse=True)
C=Counter(A)
ans=0
for a in A:
    if C[a]==0:
        continue
    C[a]-=1
    t=2**a.bit_length()-a
    if C[t]:
        C[t]-=1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main(l):
    counts = {}
    answer = 0
    for nb in l:
        counts[nb] = counts.get(nb, 0) + 1
    for a in sorted(counts.keys(), reverse=True):
        b = (1 << a.bit_length()) - a
        c_a = counts[a]
        c_b = counts.get(b)
        if c_b:
            if a == b:
                answer += c_a // 2
            else:
                increment = c_a if c_a < c_b else c_b
                counts[a] -= increment
                counts[b] -= increment
                answer += increment

    return answer


if __name__ == '__main__':
    input()
    print(main(map(int, input().split())))

Submission status: Accepted

Solution code:
input()
nbs = map(int, input().split())

answer = 0
count = {}

for nb in nbs:
    count[nb] = count.get(nb, 0) + 1

for nb in sorted(count.keys(), reverse=True):
    searching = (1 << nb.bit_length()) - nb
    nb_count = count[nb]
    sr_count = count.get(searching, 0)
    if sr_count:
        if nb == searching:
            increment = nb_count // 2
        else:
            increment = nb_count if nb_count < sr_count else sr_count
            count[searching] -= increment
        answer += increment

print(answer)

Submission status: Accepted

Solution code:
#AGC030 B - Powers of two
import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv==2*a and cnter[inv-a]<=1:
      	continue
    if cnter[inv-a]>0:
        cnter[inv-a]=cnter[inv-a]-1
        cnter[a]=cnter[a]-1
        ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
cnt = Counter(A)
for a in A:
    if cnt[a] == 0:
        continue
    cnt[a] -= 1
    b = 2**a.bit_length() - a
    if cnt[b] > 0:
        ans += 1
        cnt[b] -= 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import Counter

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

two_bekis = [2**i for i in range(31)]

ans = 0
cnt = Counter(A)
seta = set(A)
for i, a in enumerate(reversed(A)):
    b = two_bekis[bisect.bisect_right(two_bekis, a)] - a
    if b not in seta:
        continue

    if a == b and cnt[a] >= 2:
        ans += 1
        cnt[a] -= 2
    elif a != b and cnt[a] >= 1 and cnt[b] >= 1:
        ans += 1
        cnt[a] -= 1
        cnt[b] -= 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import Counter

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


two_bekis = []
tmp = 1
while tmp < 2*10**9:
    two_bekis.append(tmp)
    tmp *= 2

ans = 0
cnt = Counter(A)
seta = set(A)
for i, a in enumerate(reversed(A)):
    idx = bisect.bisect_right(two_bekis, a)
    two_beki = two_bekis[idx]
    b = two_beki - a
    if b not in seta:
        continue

    if a == b and cnt[a] >= 2:
        ans += 1
        cnt[a] -= 2
    elif a != b and cnt[a] >= 1 and cnt[b] >= 1:
        ans += 1
        cnt[a] -= 1
        cnt[b] -= 1
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
numberList = []
numberList = list(map(int, input().split(" ")))
numberList.sort(reverse=True)
numberDict = {}

for number in numberList:
    if number not in numberDict:
        numberDict[number] = 0
    numberDict[number] += 1

ret = 0

for number in numberList:
    if numberDict[number] > 0:
        numberDict[number] -= 1
#        print(number)
#        print(math.log(number,2))
        gap = 2 ** (int(math.log(number, 2)) + 1) - number
        if gap in numberDict and numberDict[gap] > 0:
            numberDict[gap] -= 1
            ret += 1

print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict

N=int(input())
A=[int(x) for x in input().split()]
A.sort(reverse=True)

cnt=defaultdict(int)
for a in A:
  cnt[a]+=1

P2=[]
for i in range(1,32):
  P2.append(2**(32-i))

ans=0

for a in A:
  for b in P2:
    if a >= b or cnt[a] < 1:
      break
    else:
      if (cnt[b-a] > 0 and (b-a) != a) or (cnt[b-a] > 1 and (b-a) == a):
        ans+=1
        cnt[b-a]-=1
        cnt[a]-=1
        break

print(ans)

Submission status: Accepted

Solution code:
import collections
def hoge(n):
    k = 1    
    while k<=n:
        k*=2
    return k-n
ans = 0
input()
a = [int(x) for x in input().split()]
c = collections.Counter(a)
sa = list(set(a))
sa.sort()
sa.reverse()
for i in range(len(sa)):
    x = sa[i]
    if c[x]<= 0:
        continue    
    y = hoge(x)
    if x==y:
        ans += c[x]//2
    elif c[y]>= 0:
        ans += min(c[x],c[y])
        c[y] -=c[x]
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    r = 0
    ii = 2**32
    for k in sorted(d.keys(), reverse=True):
        while k < ii // 2:
            ii //= 2
        if k * 2 == ii:
            r += d[k] // 2
        else:
            t = ii - k
            u = min(d[t], d[k])
            r += u
            d[t] -= u
    return r


print(main())

Submission status: Accepted

Solution code:
from collections import Counter

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

inputs.sort(reverse=True)
counter_inputs = Counter(inputs)
powers_of_two = [2**i for i in range(1, 31)]
ans = 0

for item in inputs:
    if counter_inputs[item] > 0:
        counter_inputs[item] -= 1
    
        while powers_of_two[-1] > 2 * item:
            powers_of_two.pop(-1)
        
        pair = powers_of_two[-1] - item
        if counter_inputs[pair] > 0:
            ans += 1
            counter_inputs[pair] -= 1
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
from collections import Counter

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
A_count = dict(Counter(A_list))

ans = 0
for i in range(N-1, -1, -1):
    if A_count[A_list[i]] <= 0:
        continue
    A_count[A_list[i]] -= 1
    if (A_list[idx[i]] == cand_A[i]) and (A_count[cand_A[i]] > 0):
        ans += 1
        A_count[cand_A[i]] -= 1

print(ans)

Submission status: Accepted

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

cnt = {}
for n in a:
    cnt[n] = cnt.get(n, 0) + 1

ans = 0
for n in a:
    g = 2 ** n.bit_length()
    s = g - n
    if n == s:
        pair = cnt.get(s, 0) // 2
        ans += pair
        cnt[s] = cnt.get(s, 0) % 2
    else:
        pair = min(cnt.get(n, 0), cnt.get(s, 0))
        ans += pair
        cnt[n] = cnt.get(n, 0) - pair
        cnt[s] = cnt.get(s, 0) - pair
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort(reverse=True)
C = Counter(A)
m = 1 << 30
ans = 0

for a in A:
    if C[a] <= 0:
        continue
    C[a] -= 1
    while m > a * 2:
        m >>= 1
    v = m - a
    if v in C and C[v] > 0:
        C[v] -= 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import collections


def run(N, A):
    cnt = 0
    beki = [2**i for i in range(1, 32)]
    A = sorted(A, reverse=True)
    used = collections.Counter(A)
    for a in A:
        if used[a] == 0:
            continue
        used[a] -= 1
        while beki[-1] > 2*a:
            beki.pop(-1)
        if used[beki[-1] - a] >= 1:
            cnt += 1
            used[beki[-1] - a] -= 1
    return cnt


def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(run(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for k in range(N-1,1,-1):
    if A[k]==int(A[k]):
        b = 1
        while b <= A[k]:
            b *= 2
        p = bisect.bisect_left(A,b-A[k])
        if p != k and A[p]+A[k] == b:
            ans += 1
            A[k] += 0.9
            A[p] -= 0.9
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
from math import log2
n = int(input())
a = [int(i) for i in input().split()]
a,x,ans = sorted(a),[1]*n,0
for i in range(n-1,-1,-1):
	if x[i]:
		m = 2**(int(log2(a[i]))+1)
		b = bisect(a,m-a[i],hi=i)-1
		if b+1 and a[b]==m-a[i]: x[b],ans,a[b],a[i] = 0,ans+1,a[b]+0.1,a[i]+0.1
print(ans)

Submission status: Accepted

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

used = collections.Counter(a)
a.sort()
a.reverse()

two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1

counter = 0
for i in range(n):
    if used[a[i]] > 0:
        used[a[i]] -= 1
        while two[-1] > 2*a[i]:
            two.pop(-1)

        if used[two[-1]-a[i]] >= 1:
            counter += 1
            used[two[-1]-a[i]] -= 1

print(counter)

Submission status: Accepted

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] and 1<= ballDictBox[getBallNumber]):
			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: Accepted

Solution code:
import sys
import math
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

def check_t(num):
    t = math.log(num,2)
    return 2**(int(t)+1)



from collections import defaultdict
n = getN()
nums = getlist()
numhash = defaultdict(int)
for i in nums:
    numhash[i] += 1
ans = 0
for num in sorted(numhash.keys(), key=lambda x: -x):
    while(numhash[num] != 0):
        target = (check_t(num)) - num
        if numhash[target]:

            if target == num:
                if numhash[target] >= 2:
                    ans += 1
                    numhash[target] -= 2
                else:
                    numhash[num] = 0
            else:
                if numhash[target] >= 1:
                    ans += 1
                    numhash[target] -= 1
                    numhash[num] -= 1
                else:
                    numhash[num] = 0
        else:
            numhash[num] = 0


print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

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

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

a_list = reversed(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: Accepted

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 in sorted(d.keys(), reverse=True):
    l = 2**int(math.log(k, 2) + 1) - k
    v = d[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] = w-v
print(c)

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]

count = 0
items = {}
for a in A_list:
    if a in items.keys():
        items[a] += 1
    else:
        items[a] = 1
A_list.sort(reverse=True)
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: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]
count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1
 
    else:
        items[a] = 1
A_list.sort(reverse=True)
 
for a in A_list:
    if items[a] >= 1:
 
        for t in two_list:
            m = t -a
            if m in items:
                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: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1

    else:
        items[a] = 1
A_list.sort(reverse=True)

for a in A_list:
    if items[a] >= 1:
        for t in two_list:
            m = t - a
            if m in items:
                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: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(As)
As.sort(reverse=True)

Ps = [2]
for i in range(29):
    Ps.append(Ps[-1] * 2)

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1

    while Ps[-1] > 2 * A:
        Ps.pop()

    if cnt[Ps[-1] - A] > 0:
        ans += 1
        cnt[Ps[-1] - A] -= 1

print(ans)

Submission status: Accepted

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(start,len(t)):
        if t[j] > 2*x[i]:
            start = j
        if t[j] < x[i]:
            break
        if t[j]-x[i] in c.keys():
            if t[j]-x[i] == x[i]:
                if c[x[i]] >= 2:
                    c[x[i]] -= 2
                    count +=1
            else:
                if 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: Accepted

Solution code:
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))[-1::-1]
c = Counter(A)
ans = 0
for a in A:
    b = (1<<a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1
print(ans)

Submission status: Accepted

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:
    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: Accepted

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

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

n=i1()
a=i2()
from collections import defaultdict
d = defaultdict(int)
for i in a:
 d[i]+=1
a.sort()
import math
f=0
for i in range(n)[::-1]:
 if d[a[i]]>0:
  x=2**(int(math.log2(a[i]))+1)-a[i]
  d[a[i]]-=1
  if d[x]>0:
    d[x]-=1
    f+=1
  else:
    d[a[i]]+=1
print(f)

Submission status: Accepted

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

memo = collections.defaultdict(lambda : 0)

for i in a:
    memo[i] = memo[i] + 1

b = sorted(memo.keys(), reverse=True)

ret = 0
pot = [1] * 35
for i in range(len(pot)-1):
    pot[i+1] = pot[i] * 2

for i in b:
    for j in range(34, -1, -1):
        if pot[j] - i <= 0:
            t = pot[j+1] - i
            break

    if i == t:
        ret += memo[i] // 2
    else:
        c = min([memo[i], memo[t]])
        memo[t] -= c
        ret += c

print(ret)

Submission status: Accepted

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=29
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: Accepted

Solution code:
import collections
import math
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  j=int(math.log2(i))+1
  k=2**j-i
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
from math import log,floor
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
C = Counter(A)

cnt = 0
last_a = -1
for i in range(N):
  a = A[i]
  if last_a == a:
    continue
  last_a = a
  count_a = C[a]
  if count_a <= 0:
    continue
  b = pow(2,floor(log(a)/log(2))+1) - a
  count_b = C[b]
  if count_b <= 0:
    continue
  i += count_a - 1
  x = min(count_a, count_b) if a != b else count_a // 2
  cnt += x
  C[a] -= x
  C[b] -= x
  
print(cnt)

Submission status: Accepted

Solution code:
import bisect
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
 
res = 0
for i in range(n - 1 , -1, -1):
    if a[i] == int(a[i]):#判定
        b = 1
        while b <= a[i]:
            b =b*2
 
        j = bisect.bisect_left(a, b - a[i])
        if i > j:
            if b - a[i] == a[j]:
                res += 1
                a[j] = a[j] - 0.5
                a[i] = a[i] + 0.5
print(res)

Submission status: Accepted

Solution code:
# cook your dish here
from collections import Counter
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
c = Counter(a)

res = 0
for x in a:
    b = 1
    while b <= x:
        b = b*2
    p = b-x
    if p in c.keys():
        if p == x and c[x] >= 2:
            c[x] = c[x] - 2
            res += 1
        elif p != x and c[x] > 0 and c[p] > 0:
            c[x] -= 1
            c[p] -= 1
            res += 1
    
print(res)

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort(reverse=True)
c = Counter(A)
res = 0
for a in A:
    n = 2 ** a.bit_length() - a
    if n in c.keys():
        if a == n and c[a] > 1:
            c[a] -= 2
            res += 1
        elif a != n and c[a] > 0 and c[n] > 0:
            c[a] -= 1
            c[n] -= 1
            res += 1
    
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
c = Counter(A)
ans = 0
# 大きいものからペアを探す
# 選択する数をx,ペアをyとする(1 <= y <= x)
# x < x+y <= 2*x よりxに対してx+yが2のべき乗となるようなものは一意に定まる
# したがってyも一意に定まるので,あとはyを探してくる
# x,yのペアが見つかれば1カウント
for e in A:
# x == y のとき １ループで2個減っているのでチェックする前にc[e] == 0となる可能性あり
    if c[e] == 0:
        continue
    c[e] -= 1
    pair = pow(2,e.bit_length()) - e
    if c[pair] >= 1:
        ans += 1
        c[pair] -= 1
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = sorted([int(_) for _ in input().split()], reverse=True)
dp = {}
for a in A:
    dp[a] = dp.get(a, 0) + 1
ans = 0
for a in A:
    if dp[a]:
        dp[a] -= 1
        if dp.get(2**int(math.log2(a) + 1) - a, 0) > 0:
            dp[2**int(math.log2(a) + 1) - a] -= 1
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if b in c.keys():
        if a == b and c[a] > 1:
            c[a] -= 2
            ans += 1
        elif a != b and c[a] > 0 and c[b] > 0:
            c[a] -= 1
            c[b] -= 1
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from bisect  import bisect_left

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

sum = 0
for i in range (len(a)-1,-1,-1):

    b = 1
    while b <= a[i]:
        b = b<<1
    t = b - a[i]
    #print("2^",t)

    k = bisect_left(a,t)
    if a[k] == t and k < i:
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
print(sum)

Submission status: Accepted

Solution code:
import collections

N = input()
A = map(int, raw_input().split())
C = collections.Counter(A)
K = C.keys()
K.sort(reverse=1)
res = 0
for i in K:
    for j in xrange(60):
        p = 2 ** j
        if i <= p:
            break
    if i == p:
      res += C[i] // 2
      C[i] = C[i] // 2 * 2
    else:
      num = min(C[i], C[p - i])
      res += num
      C[i] -= num
      C[p - i] -= num
print res

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
nums = sorted(list(map(int, input().split())), reverse=True)

num_map = Counter(nums)

answer = 0
for num in nums:
    pair = (1 << (num.bit_length())) - num

    if num_map[num] > 0 and num_map[pair]:
        if num == pair and num_map[num] > 1:
            answer += 1
            num_map[num] -= 2
        if not num == pair:
            answer += 1
            num_map[num] -= 1
            num_map[pair] -= 1

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
nums = sorted(list(map(int, input().split())), reverse=True)

num_map = Counter(nums)

answer = 0
for num in nums:
    pair = (1 << (num.bit_length())) - num

    if num_map[num] > 0 and num_map[pair]:
        if num == pair and num_map[num] > 1:
            answer += 1
            num_map[num] -= 2
        if num > pair:
            answer += 1
            num_map[num] -= 1
            num_map[pair] -= 1

print(answer)

Submission status: Accepted

Solution code:

#偶奇合わせてたのはグルグル回してたからだが
#一意に決めるんなら偶奇合わせる必要ないのでは
def 解():
    N = int(input())
    dA ={}
    def lenbin(a):
        return len(bin(a)) - 2
    def addData(oDict,a):
        if a in oDict:
            oDict[a]+=1
        else:
            oDict[a]=1
    for a in map(int,input().split()):
        addData(dA,a)
    def searchPair(oD):
        iC = 0
        for a in sorted(oD.keys(),reverse=True):
            if oD[a]:
                t = ( 1 << lenbin(a)) - a
                if t == a:
                    iAT = oD[a] // 2
                    iC += iAT
                    oD[a] -= iAT *2
                elif t in oD:
                    iAT = min(oD[a],oD[t])
                    iC += iAT
                    oD[a] -= iAT
                    oD[t] -= iAT
        return iC
    print(searchPair(dA))
解()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if (memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 0 and (1 << (len(bin(a[i])) - 2)) - a[i] != a[i]) or memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 1:
        memo[a[i]] -= 1
        memo[(1 << (len(bin(a[i])) - 2)) - a[i]] -= 1
        count += 1

print(count)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[2**i for i in range(1,35)]
table=[True]*N
A.sort()
ans=0
for t in T[::-1]:
  l,r=0,N-1
  while l<r:
    if A[l]+A[r]>t:
      r-=1
    elif A[l]+A[r]==t:
      if table[l] and table[r]:
        ans+=1
        table[l],table[r]=False,False
      if not table[l]:
        l+=1
      if not table[r]:
        r-=1
    elif A[l]+A[r]<t:
      l+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dA1 ={}
dA0 ={}
def lenbin(a):
    return len(bin(a)) - 2
def addData(oDict,a):
    if a in oDict:
        oDict[a]+=1
    else:
        oDict[a]=1
for a in input().split():
    a = int(a)
    if a % 2 :
        addData(dA1,a)
    else:
        addData(dA0,a)
def searchPair(oD):
    iC = 0
    for a in sorted(oD.keys(),reverse=True):
        t = ( 1 << lenbin(a)) - a
        if t == a:
            iAT = oD[a] // 2
            iC += iAT
            oD[a] -= iAT *2
        elif t in oD:
            iAT = min(oD[a],oD[t])
            iC += iAT
            oD[a] -= iAT
            oD[t] -= iAT
    return iC
#iC = 0
#iC += searchPair(dA1)
#iC += searchPair(dA0)
print(searchPair(dA1)+searchPair(dA0))

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort(reverse=True)
c = Counter(A)

ans = 0
flag = False
for i in range(n):
    if c[A[i]] == 0:
        continue

    pow_2 = 2 ** len(format(A[i], "b"))
    if c[pow_2 - A[i]] > 0 and pow_2 - A[i] != A[i]:
        c[pow_2 - A[i]] -= 1
        c[A[i]] -= 1
        ans += 1
    elif c[pow_2 - A[i]] > 1 and pow_2 - A[i] == A[i]:
        if flag is True:
            c[A[i]] -= 2
            ans += 1
            flag = False
        else:
            flag = True

print(ans)

Submission status: Accepted

Solution code:
import math

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

D = {}
for i in A :
    if i not in D : D[i] = 1
    else: D[i] += 1

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