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:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    d=A[-1-i]
    f=len(bin(d))-2
    e=2**f-d
    if D[e]>0:
      cnt+=1
      D[e]-=1
print(cnt)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a = list(map(int, input().split()))
  
  a.sort()
  
  border = []
  
  key = 2
  for i in range(n):
    while key <= a[i]:
      border.append(i)
      key *= 2
  
  border.append(n)
  border.reverse()
  
  ans = 0
  already = [False]*n
  for v in border:
    index = 0
    for i in range(v-1, -1, -1):
      if already[i]:
        continue
      while index < i and (a[i]+a[index] < key or already[index]):
        index += 1
      if index == i:
        break
      if a[i]+a[index] == key:
        already[i] = True
        already[index] = True
        ans += 1
    
    key //= 2
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    counter = Counter(a)

    keys = list(counter.keys())
    keys.sort(reverse=True)

    ans = 0

    for num1 in keys:
        c1 = counter[num1]
        x = 1
        while x <= num1:
            x *= 2
        num2 = x - num1
        if num1 == num2:
            cnt = c1 // 2
            ans += cnt
            counter[num1] -= cnt * 2
        else:
            c2 = counter[num2]
            cnt = min(c1, c2)
            ans += cnt
            counter[num1] -= cnt
            counter[num2] -= cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
import bisect as bi
Q=deque(A)
rui=[pow(2,i) for i in range(31)]
ans=0
C=Counter(A)
# N={ i:0 for i in C.keys() }
while Q:
    k=Q.pop()
    if C[k]==0:continue
    for r2 in rui:
        if r2>2*k:break
        if C.get(r2-k,None)==None:continue
        if r2-k==k: 
            if C[k]<=1:continue
        if C[r2-k]==0: continue
        C[r2-k]-=1;C[k]-=1;ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを考え
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        b = pow2[a.bit_length()] - a
        if counter[b] == 0:
            continue
        cnt = min(counter[a], counter[b])
        ans += cnt
        counter[a] -= cnt
        counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
wait = defaultdict(int)
ans = 0

for Ai in A:
    if wait[Ai]>=1:
        ans += 1
        wait[Ai] -= 1
    else:
        t = 0
    
        while 2**t<=Ai:
            t += 1
    
        wait[2**t-Ai] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))[::-1]
c = Counter(a)
ans = 0
for i in range(n):
    if c[a[i]] > 0:
        m = (1 << a[i].bit_length()) - a[i]
        c[a[i]] -= 1
        if c[m] > 0:
            c[m] -= 1
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

C = Counter(A)
A.sort(reverse=True)
ans = 0
for i in range(N):
    x = A[i]
    if C[x] > 0:
        y = 2**x.bit_length() - x
        C[x] -= 1
        if C[y] > 0:
            C[y] -= 1
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import*
C=Counter(a:=sorted(map(int,[*open(r:=0)][1].split())))
for x in a[::-1]:
 if C[x]>0:y=2**x.bit_length()-x;C[x]-=1;r+=C[y]>0;C[y]-=1
print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
A = list(int(x) for x in input().split())

count = defaultdict(int)
for a in A:
    count[a] += 1
A = sorted(set(A))

ans = 0
for a in reversed(A):
    t = a.bit_length()
    pair = 2**t - a
    if pair == a:
        ans += count[a] // 2
        count[a] -= count[a] // 2
    else:
        k = min(count[a], count[pair])
        ans += k
        count[a] -= k
        count[pair] -= k

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
jisho = defaultdict(int)
for a in A:
    jisho[a] += 1
A.sort()
ans = 0
for i in range(n - 1, -1, -1):
    num = A[i]
    if jisho[num] == 0:
        continue
    jisho[num] -= 1
    temp = num // (num & -num)
    keta = temp.bit_length()
    kouho = 1
    for i in range(1, keta):
        if (temp >> i) & 1 == 0:
            kouho += 1 << i
    kouho *= num & -num
    if jisho[kouho] > 0:
        # print(num, kouho)
        jisho[kouho] -= 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ca=dict(Counter(a))
a.sort()
ans=0
for i in range(n):
  x=a[-1-i]
  tmp=pow(2,len(bin(x))-2)-x
  if x==tmp:
    if ca[x]>=2:
      ca[x]-=2
      ans+=1
  elif ca[x] and tmp in ca and ca[tmp]>0:
    ans+=1
    ca[tmp]-=1
    ca[x]-=1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter, defaultdict
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
vs = vs[::-1]
# print(c)
for k in c:
    for v in vs:
        if k<v and v-k in c and c[v-k]>0:
            if k==v-k:
                ans += c[k]//2
                c[k] = c[k]%2
            elif c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    ac = collections.Counter(A)
    num_pairs = 0
    for i in range(N - 1, 0, -1):
        x = A[i]
        if ac[x] <= 0:
            continue
        p = 1
        while p <= x:
            p <<= 1
        j = bisect.bisect_left(A, p - x, 0, i)
        if j >= i:
            continue
        y = A[j]
        if x + y != p:
            continue
        ac[x] -= 1
        if ac[y] <= 0:
            continue
        ac[y] -= 1
        num_pairs += 1
    return num_pairs


print(solve())

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

balls_count = defaultdict(int)

N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
ans = 0
beki_list = [pow(2, i) for i in range(1, 32)]
for a in A:
    balls_count[a] += 1

for a in A:
    if balls_count[a] == 0:
        continue
    balls_count[a] -= 1
    index = bisect_right(beki_list, a)
    pair = beki_list[index] - a
    if balls_count[pair] > 0:
        balls_count[pair] -= 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int,input().split()))
a2 = list(set(a))
a2.sort(reverse=True)

d = defaultdict(int)
for i in a:
    d[i] += 1

ans = 0
for i in a2:
    next = 2**(i-1).bit_length()
    if(i==next):
        ans += d[i]//2
    else:
        pair = min(d[i],d[next-i])
        d[next-i] -= pair
        ans += pair
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
ans = 0

D = defaultdict(int)
for x in A:
    D[x] += 1
A.sort(reverse=True)

for x in A:
    for i in range(1, 31):
        if D[x] > 0:
            if 2**i-x in D.keys() and D[2**i-x] > 0:
                if 2**(i-1) != x:
                    ans += 1
                    D[x] -= 1
                    D[2**i-x] -= 1
for i in range(31):
    ans += D[2**i]//2
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

# 残った数の中で最大の数とペアになれる（可能性のある）数は一意に決まる。
# 15に15以下の数を足して作れる2べきは16だけ、32は作れない。
# 8 * 2 < 15 * 2 < 16 * 2だから。
# 大きいほうから見ていって、ペアになれる数を特定出来たらペアにする。
# 以下を別々で持つ
# ・大きい順の管理
# ・探している数へのO(1)での到達と、残数管理（同じ数が複数回出てくる可能性があるため）

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

from collections import defaultdict

balls_count = defaultdict(int) # 個数の管理

for a in A:
  balls_count[a] += 1

A = sorted(A, reverse = True)

def get_pair_num(x): # xとペアになれる数を探す
  tar = 2
  while tar < x:
    tar *= 2
  if tar == x:
    return tar
  return tar - x

ans = 0
for ball in A:
  if balls_count[ball] == 0: # すでに使用済みのボールである
    continue
  # 取り出した時点で、このあとペアにするか破棄するかのどちらかである。
  # 同じボールを取り出すことのないよう、この時点で1引いておく
  balls_count[ball] -= 1
  pair = get_pair_num(ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

# 残った数の中で最大の数とペアになれる（可能性のある）数は一意に決まる。
# 15に15以下の数を足して作れる2べきは16だけ、32は作れない。
# 8 * 2 < 15 * 2 < 16 * 2だから。
# 大きいほうから見ていって、ペアになれる数を特定出来たらペアにする。
# 以下を別々で持つ
# ・大きい順の管理
# ・探している数へのO(1)での到達と、残数管理（同じ数が複数回出てくる可能性があるため）

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

from collections import defaultdict

balls_count = defaultdict(int) # 個数の管理

import heapq as hq
balls_q = [] # ボールを大きい順に入れていく

for a in A:
  balls_count[a] += 1
  hq.heappush(balls_q, -a)

def get_pair_num(x): # xとペアになれる数を探す
  tar = 2
  while tar < x:
    tar *= 2
  if tar == x:
    return tar
  return tar - x

ans = 0
while balls_q:
  ball = -(hq.heappop(balls_q))
  if balls_count[ball] == 0: # すでに使用済みのボールである
    continue
  # 取り出した時点で、このあとペアにするか破棄するかのどちらかである。
  # 同じボールを取り出すことのないよう、この時点で1引いておく
  balls_count[ball] -= 1
  pair = get_pair_num(ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1
  # pushしないからheapqでなくてよかったな・・・

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
dic = defaultdict(int) #初期化する関数。

N = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
#B = set(A)
for i in A:
  dic[i] +=1

beki = [1]
for i in range(32): #30に変更
  temp = beki[-1]
  beki.append(temp*2)
#print(beki)
L = [[] for _ in range(N)]
for i in range(N):
  for t in beki:
    now = t-A[i]
    if A[i] == now and dic[now] >=2:
      L[i].append(now)
    elif A[i] != now and now>0 and now in dic:
      L[i].append(now)
  L[i].append(A[i]) #自分を足しておく

#L.sort(key=len)
#print(L)
#print(dic)
ans = 0
for i in range(N):
  now = L[i].pop()
  #print(L[i],dic)
  for num in L[i]:
    if num in dic:
      if num == now and dic[now] > 1:
        dic[num] -=2
        ans += 1
        break
      elif num != now and dic[num] > 0 and dic[now] > 0:
        dic[num] -= 1
        dic[now] -= 1
        ans += 1
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    nums = getList()
    stock = defaultdict(int)
    for num in nums:
        stock[num] += 1

    # print(stock)
    ans = 0
    for i in range(32, -1, -1):
        tgt = 2 ** i
        # print(tgt)
        d = defaultdict(int)
        for num in nums:
            d[tgt - num] += 1
        # print(d)
        for dk in d.keys():
            if dk * 2 == tgt:
                a = stock[dk] // 2
                ans += a
                stock[dk] -= 2 * a
            else:
                # print(dk)
                if dk in stock:
                    # print("--")
                    # print(stock, dk, tgt)
                    a = min(stock[tgt - dk], stock[dk])
                    ans += a
                    stock[dk] -= a
                    stock[tgt - dk] -= a


    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
a.reverse()
s={}
for i in a:
  if i in s:
    s[i]+=1
  else:
    s[i]=1
i=0
current=40
l=0
ans=0
while current!=0 and i<n:
  l=i
  while a[i]>=pow(2,current-1):
    i+=1
    if i==n:
      break
  r=i
  for j in range(l,r):
    if s[a[j]]==0:
      continue
    if pow(2,current)-a[j] in s:
      if a[j]==pow(2,current-1):
        if s[a[j]]>=2:
          ans+=1
          s[a[j]]-=2
      else:
        if s[pow(2,current)-a[j]]>0:
          s[pow(2,current)-a[j]]-=1
          s[a[j]]-=1
          ans+=1
  current-=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
#N = 4
#A = [2,2,4,4,4,4,12,12,12]

A.sort()
cnt = Counter(A)
keys = sorted(cnt.keys(), reverse=True)

ans = 0
for a in keys:
    p = len(bin(a)) - 2
    t = (1 << p) - a
    if a == t:
        d = cnt[a]//2
        ans += d
        cnt[a] -= 2*d
        continue
    if t in cnt:
        d = min(cnt[t],cnt[a])
        ans += d
        cnt[t] -= d
        cnt[a] -= d
print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = list(map(int,ipt().split()))
    a.sort(reverse=True)
    d = defaultdict(int)
    ans = 0
    for i in a:
        if d[i]:
            ans += 1
            d[i] -= 1
        else:
            nl = len(format(i,"b"))
            d[(i^(2**(nl)-1))+1] += 1

    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import bisect

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

    A.sort()
    counter = Counter(A)
    ch = [True] * n

    beki = []
    c = 1
    for _ in range(31):
        beki.append(c)
        c *= 2

    # print(counter)
    ans = 0
    for i in range(n-1,-1,-1):
        a = A[i]
        j = bisect.bisect_right(beki,a)
        t = beki[j] - a
        # print(t,a)
        if t == a:
            m = counter[a]//2
        elif t < a:
            m = min(counter[a],counter[t])

        counter[a] -= m
        counter[t] -= m
        ans += m
    print(ans)

main()

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(int)

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

ans=0
for num in sorted(d,reverse=True):
    while d[num]>=1:
        d[num]-=1

        now=1
        while now<=num:
            now*=2

        cand = now - num
        if d[cand]>=1:
            d[cand]-=1
            ans+=1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())),reverse=1)
from collections import Counter as co
d=co(l)
ans=0
for i in l:
    x=pow(2,i.bit_length())-i

    if d[i]>0 and x in d and d[x]>0:
        if x!=i:d[x]-=1;ans+=1;d[i]-=1
        elif d[i]>=2:d[i]-=2;ans+=1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from bisect import bisect_right

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

N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1

A = [-a for a in A]
heapify(A)
ans = 0
while A:
  a = - heappop(A)
  if d[a] == 0:
    continue
  pair = pow2[bisect_right(pow2, a)] - a
  if a == pair:
    if d[a] >= 2:
      d[a] -= 2
      ans += 1
  elif pair in d and d[pair] > 0:
    ans += 1
    d[pair] -= 1
    d[a] -= 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=0
maxa=max(a)
while 2**cnt<2*maxa:
    cnt+=1
    # print(2**cnt)

lsta=[0]*n
ans=0
for i in range(1,cnt+1)[::-1]:
    dic=defaultdict(list)
    for j in range(n):
        if 2**i>a[j] and lsta[j]==0:
            if dic[a[j]]!=[]:
                lsta[j]=-1
                lsta[dic[a[j]].pop()]=-1
                ans+=1
            else:
                dic[2**i-a[j]].append(j)
    # print(dic)
# print(lsta)
# ans=-sum(lsta)//2
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=0
maxa=max(a)
while 2**cnt<2*maxa:
    cnt+=1
    # print(2**cnt)

lsta=[0]*n
for i in range(1,cnt+1)[::-1]:
    dic=defaultdict(list)
    for j in range(n):
        if 2**i>a[j] and lsta[j]==0:
            if dic[a[j]]!=[]:
                lsta[j]=-1
                lsta[dic[a[j]].pop()]=-1
            else:
                dic[2**i-a[j]].append(j)
    # print(dic)
# print(lsta)
ans=-sum(lsta)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import log2

def find(x):
    f = 2**(int(log2(x))+1)-x
    if f <= x:
        return f
    return 0

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
c = Counter(a)
ans = 0

for i in range(n):
    f = find(a[i])
    if f == a[i]:
        m = c[a[i]]//2
    else:
        m = min(c[a[i]],c[f])
    c[a[i]] -= m
    c[f] -= m
    ans += m
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from collections import Counter

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

power = 1
powers = [1]
while power <= 10 ** 9:
    power *= 2
    powers.append(power)

a.sort()
c = Counter(a)

ans = 0
for e in a[::-1]:
    i = bisect_right(powers, e)
    target = powers[i]

    if target == 2 * e:
        if c[e] >= 2:
            c[e] -= 2
            ans += 1

    else:
        if c[e] and c[target-e]:
            c[e] -= 1
            c[target-e] -= 1
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
while n <= 2 * A[0]:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        if b < 0:
            continue
        if b > a:
            break
        c = 0
        if b == a and cnt[a] > 1:
            c = cnt[a] // 2
        elif b != a and cnt[b] > 0:
            c = min(cnt[a], cnt[b])
        cnt[a] -= c
        cnt[b] -= c
        ans += c
    n //= 2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = Counter(a)
ans = 0

def make(x):
    num = 1
    while num <= x:
        num *= 2
    return num

for i in range(n):
    x = make(a[i])
    if cnt[x - a[i]] > 0 and cnt[a[i]] > 0 and x != 2 * a[i]:
        ans += 1
        cnt[x - a[i]] -= 1
        cnt[a[i]] -= 1
    elif x == 2 * a[i] and cnt[a[i]] > 1:
        ans += 1
        cnt[a[i]] -= 2

print(ans)

Submission status: Accepted

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
l=[]
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#print(l)
n=len(l)
ans=0
cnt=0
d=dict(l)
#print(d)
ans=0
for i in range(31,0,-1):
    piv=pow(2,i)
    cnt=0
    for j in range(n):
        val1=d.get(l[j][0])
        val2=d.get(piv-l[j][0])
        if (val1!=None)and(val2!=None):
            add=min(val1,val2)
            if l[j][0]==piv-l[j][0]:
                add=(add//2)
                ans=ans+add
                add=add*2
            else:
                ans=ans+add
            d[l[j][0]]=val1-add
            d[piv-l[j][0]]=val2-add
        #print(d)
        #input()
    #ans=ans+(cnt-c[piv//2])//2
    #print(i,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,*A = map(int, open(0).read().split())
Cnt = Counter(A)
m = 2**31
ans = 0
for i in range(31):
  for k in Cnt.keys():
    if Cnt[k]==0:
      continue
    if k==m-k:
      ans += Cnt[k]//2
      Cnt[k] %= 2
    else:
      if Cnt[m-k]==0:
        continue
      if Cnt[k]<Cnt[m-k]:
        ans += Cnt[k]
        Cnt[m-k] -= Cnt[k]
        Cnt[k] = 0
      else:
        ans += Cnt[m-k]
        Cnt[k] -= Cnt[m-k]
        Cnt[m-k] = 0
  m >>= 1
print(ans)

Submission status: Accepted

Solution code:
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
a=0
for i in range(30,0,-1):
    t=2**i
    if t//2 in d:
        a+=d[t//2]//2
        if d[t//2]%2:
            d[t//2]=1
        else:
            d.pop(t//2)
    for n,v in d.items():
        if n>=t//2:
            continue
        if t-n in d:
            w=d[t-n]
            if v>w:
                a+=w
                d[n]=v-w
                d[t-n]=0
            else:
                a+=v
                d[t-n]=w-v
                d[n]=0    
print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    find = twosum(i)
    if d[i] <= 0:
        continue
    d[i] -= 1
    if d[find] <= 0:
        d[i] += 1
    else:
        ans += 1
        d[find] -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    d[i] -= 1
    find = twosum(i)
    if d[find] > 0 and d[i] >= 0:
        ans += 1
        d[find] -= 1
    else:
        d[i] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())),reverse=1)
b=Counter(a)
cnt=0
for i in range(n):
    if b[a[i]]<=0:
        continue
    k=a[i].bit_length()
    x=(1<<k)-a[i]
    if x==a[i]:
        if b[x]>1:
            cnt+=1
            b[x]-=2
    elif x in b and b[x]>0:
        cnt+=1
        b[a[i]]-=1
        b[x]-=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n = int(input())
a = sorted(list(map(int, input().split())))
d = defaultdict(int)
for i in a:
  d[i] += 1
ans = 0
for i in a[::-1]:
  d[i] -= 1
  find = twosum(i)
  if d[find] > 0 and d[i] >= 0:
    ans += 1
    d[find] -= 1
  else:
    d[i] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    pow_of_2 = [1]
    while pow_of_2[-1] < 2 * 10 ** 9:
        pow_of_2.append(pow_of_2[-1] * 2)
    
    A.sort(reverse=True)
    counter = defaultdict(int)
    for ai in A:
        counter[ai] += 1
    
    ans = 0
    for ai in A:
        if counter[ai] == 0:
            continue
        idx = bisect_right(pow_of_2, 2 * ai) - 1
        t = pow_of_2[idx]
        aj = t - ai
        if 1 < counter[aj] or 0 < counter[aj] and ai != aj:
            ans += 1
            counter[ai] -= 1
            counter[aj] -= 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<=N:
        i*=2
    return i

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


A = sorted(A)

ans=0
D=Counter(A)

for i in reversed(range(N)):
    pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
    if D[A[i]]<=0:
        continue
    elif pair_val==A[i] and D[pair_val]>=2 or pair_val!=A[i] and  D[pair_val]>=1:
        ans+=1
        D[pair_val]-=1
        D[A[i]]-=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = sorted(LI())
cnt = Counter(A)
ans = 0
for i in range(n - 1, -1, -1):
    a = A[i]
    if cnt[a]:
        cnt[a] -= 1
        b = 2 ** a.bit_length() - a
        if cnt[b]:
            ans += 1
            cnt[b] -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
A = sorted(A, reverse=True)
ans = 0
for a in A:
    if a & (a - 1) != 0:
        cand = (1 << ((a - 1).bit_length())) - a
        if cnt[a] == 0 or cnt[cand] == 0: continue
    else:
        cand = a
        if cnt[a] < 2: continue
    ans += 1
    cnt[a] -= 1; cnt[cand] -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import heapq

n = ni()
a = na()
ls = []

for i in a:
    heapq.heappush(ls,-i)

s = {}
ans = 0

for _ in range(n):
    m = -heapq.heappop(ls)
    if m in s and s[m] > 0:
        s[m] -= 1
        ans += 1
        continue
    dif = 2**m.bit_length()-m
    if dif in s:
        s[dif] += 1
    else:
        s[dif] = 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

blist=[]
for a in alist:
  a2=a
  digit_a2=0
  while(a2>0):
    a2>>=1
    digit_a2+=1
  b=2**(digit_a2)-a
  blist.append(b)
#print(alist)
#print(blist)

dic_a={}
for a in alist:
  if a in dic_a:
    dic_a[a]+=1
  else:
    dic_a[a]=1

answer=0
for i in range(N):
  a=alist[i]
  b=blist[i]
  if a==b:
    if dic_a[a]>1:
      dic_a[a]-=2
      answer+=1
      #print(a,a)
  else:
    if dic_a[a]>0 and b in dic_a and dic_a[b]>0:
      dic_a[a]-=1
      dic_a[b]-=1
      answer+=1
      #print(a,b)
    
print(answer)