Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1 \leq A_i \leq 10^9

A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

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

Sample Input 1

3
1 2 3

Sample Output 1

1

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

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2



Sample input:
3
1 2 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort()
    nDict = dict()
    for i, a in enumerate(A):
        if a in nDict: nDict[a] += 1
        else: nDict[a] = 1

    count = 0
    for i in reversed(range(N)):
        if nDict[A[i]] == 0: continue
        k = 1
        while k < A[i]: k <<= 1
        if k - A[i] in nDict and nDict[k - A[i]] > 0:
            count += 1
            nDict[A[i]] -= 1
            nDict[k - A[i]] -= 1
    print(count)
        

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    t = 0
    while True:
        t += 1
        m = 1<<t
        if m > 10**9: break
        M = [a % m for a in A]
        C = Counter(M)
        tmp = 0
        for k,v in C.items():
            if k*k == m:
                tmp += v*(v-1)//2
                continue
            tmp += v * C[m-k]
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = Counter(A)
ans = 0
for e in C:
    t = e
    for l in range(32,0,-1):
        if 2**l-t == t:
            s = C[t]//2
            ans += s
            C[t] -= s
        else:
            if 2**l-t in C:
                s = min(C[t],C[2**l-t])
                ans += s
                C[t] -= s
                C[2**l-t] -= s
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    bi = [2**i for i in range(1, 31)]
    from collections import Counter
    ans = 0
    for tar in bi:
        B = [a % tar if a < tar else -1 for a in A]
        c = Counter(B)
        cur = 0
        for k, v in c.items():
            if k == -1:
                continue
            if tar - k in c.keys() and v + c[tar - k] >= 2:
                cur += (v + c[tar - k])//2
        ans = max(ans, cur//2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n= int(input())
lis= list(map(int,input().split()))
lis.sort(reverse=True)
ans=0
while lis:
  a =lis.pop(0)
  num = 1 << len(str(bin(a)))
  num =num-a
  if num==0:num=a
  if num in lis:
    lis.remove(num)
    ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n= int(input())
lis= list(map(int,input().split()))
lis.sort(reverse=True)
ans=0
while lis:
  a =lis.pop(0)
  num = 1 << len(bin(a))
  num =num-a
  if num==0:num=a
  if num in lis:
    lis.remove(num)
    ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
al=list(set(a))
a.sort(reverse=1)
al.sort(reverse=1)
calc=lambda a:(1<<a.bit_length())-a
d={i:calc(i) for i in a}
from collections import Counter
c=Counter(a)
ans=0
for i in al:
  if d[i]==i:ans+=c[i]*(c[i]-1)//2
  elif d[i] in c:
    m=min(c[i],c[d[i]])
    c[i]-=m
    c[d[i]]-=m
    ans+=m
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
al=list(set(a))
m=max(a).bit_length()+1
ans=0
used=set()
for i in range(m,0,-1):
  s=1<<i
  d={}
  for j in range(n):
    if j in used:continue
    if s//2<=a[j]<s:
      if s-a[j] in d:d[s-a[j]]+=1
      else:d[s-a[j]]=1
      used.add(j)
  for j in range(n):
    if j in used:continue
    if a[j] in d:
      if d[a[j]]:
        ans+=1
        d[a[j]]-=1
        used.add(j)
  if s//2 in d:ans+=d[s//2]*(d[s//2]-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n= int(input())
lis= list(map(int,input().split()))
lis.sort(reverse=True)
ans=0
while lis:
  a =lis.pop(0)
  num = 2**math.ceil(math.log(a,2))-a
  if num in lis:
    lis.remove(num)
    ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n= int(input())
lis= list(map(int,input().split()))
lis.sort(reverse=True)
ans=0
while lis:
  a =lis.pop(0)
  num = 2**math.ceil(math.log(a,2))-a
  if num in lis:
    lis.remove(num)
    ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
ans=0
for i in range(1,100):
  s=1<<i
  if s>m*2:break
  d={}
  for j in a:
    if j in d:ans+=d[j]
    if s-j in d:d[s-j]+=1
    else:d[s-j]=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
while A:
    a = A.pop()
    c[a] -= 1
    Num = 1 << (a.bit_length())
    cand = Num - a  # この値は必ずa以下になるはず
    if c[cand] > 0:
        ans += 1
        c[cand] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ans = 0
while len(A) > 1:
    a = A.pop()
    c[a] -= 1
    Num = 1 << (a.bit_length())
    cand = Num - a
    if c[cand]:
        ans += 1
        c[cand] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

N, *A = map(int, read().split())

A.sort()
a = Counter(A)
answer = 0
limit = 10 ** 9 + 1
while A:
    n = A.pop()
    if a[n] == 0:
        continue

    a[n] -= 1
    # n以上の最小の2冪
    minimum = 1 << n.bit_length()
    while minimum < limit:
        b = minimum - n
        if a[b] > 0:
            answer += 1
            a[b] -= 1

            break

        minimum *= 2

print(answer)

Submission status: Wrong Answer

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

class FordFulkerson:
    class Edge:
        def __init__(self, v, cap, rev):
            self.v = v
            self.cap = cap
            self.rev = rev

    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]
        self.used = [False] * V

    def add_edge(self, u, v, cap):
        self.G[u].append(self.Edge(v, cap, len(self.G[v])))
        self.G[v].append(self.Edge(u, 0, len(self.G[u])-1))

    # find a path
    # u: current node, t: sink node, f: current flow
    def dfs(self, u, t, f):
        if u == t:
            return f
        self.used[u] = True
        for e in self.G[u]:
            if not self.used[e.v] and e.cap > 0:
                d = self.dfs(e.v, t, min(f, e.cap))
                if d > 0:
                    e.cap -= d
                    self.G[e.v][e.rev].cap += d
                    return d
        return 0

    # find the max flow from s to t
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.used = [False] * self.V
            f = self.dfs(s, t, float('inf'))
            if f == 0:
                return flow
            flow += f

N = int(input())
A = list(map(int, input().split()))
flow = FordFulkerson(2*N+2)
# 0..N-1: right
# N..2N-1: left
s, t = 2*N, 2*N+1
for i in range(N):
    flow.add_edge(s, i, 1)
    flow.add_edge(N+i, t, 1)
idx = defaultdict(list)
for i, a in enumerate(A):
    p = 2
    while p - a <= 10**9:
        for j in idx[p-a]:
            flow.add_edge(i, N+j, 1)
        p *= 2
    idx[a].append(i)
print(flow.max_flow(s, t))

Submission status: Wrong Answer

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

class Dinic:
    class Edge:
        def __init__(self, v, cap, rev):
            self.v = v
            self.cap = cap
            self.rev = rev

    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

    def add_edge(self, u, v, cap):
        self.G[u].append(self.Edge(v, cap, len(self.G[v])))
        self.G[v].append(self.Edge(u, 0, len(self.G[u])-1))

    # calculate the shortest distance from s
    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        queue = deque()
        queue.append(s)
        while queue:
            u = queue.popleft()
            for e in self.G[u]:
                if e.cap > 0 and self.level[e.v] == -1:
                    self.level[e.v] = self.level[u] + 1
                    queue.append(e.v)

    # find a path
    def dfs(self, u, t, f):
        if u == t:
            return f
        i = self.iter[u]
        while i < len(self.G[u]):
            e = self.G[u][i]
            if e.cap > 0 and self.level[u] < self.level[e.v]:
                d = self.dfs(e.v, t, min(f, e.cap))
                if d > 0:
                    e.cap -= d
                    self.G[e.v][e.rev].cap += d
                    return d
            i += 1
            self.iter[u] += 1
        return 0

    # find the max flow from s to v
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] == -1:
                return flow
            self.iter = [0] * self.V
            f = 0
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f

N = int(input())
A = list(map(int, input().split()))
flow = Dinic(2*N+2)
# 0..N-1: right
# N..2N-1: left
s, t = 2*N, 2*N+1
for i in range(N):
    flow.add_edge(s, i, 1)
    flow.add_edge(N+i, t, 1)
idx = defaultdict(list)
for i, a in enumerate(A):
    p = 2
    while p - a <= 10**9:
        for j in idx[p-a]:
            flow.add_edge(i, N+j, 1)
        p *= 2
    idx[a].append(i)
print(flow.max_flow(s, t))

Submission status: Wrong Answer

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

class Dinic:
    class Edge:
        def __init__(self, v, cap, rev):
            self.v = v
            self.cap = cap
            self.rev = rev

    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

    def add_edge(self, u, v, cap):
        self.G[u].append(self.Edge(v, cap, len(self.G[v])))
        self.G[v].append(self.Edge(u, 0, len(self.G[u])-1))

    # calculate the shortest distance from s
    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        queue = deque()
        queue.append(s)
        while queue:
            u = queue.popleft()
            for e in self.G[u]:
                if e.cap > 0 and self.level[e.v] == -1:
                    self.level[e.v] = self.level[u] + 1
                    queue.append(e.v)

    # find a path
    def dfs(self, u, t, f):
        if u == t:
            return f
        i = self.iter[u]
        while i < len(self.G[u]):
            e = self.G[u][i]
            if e.cap > 0 and self.level[u] < self.level[e.v]:
                d = self.dfs(e.v, t, min(f, e.cap))
                if d > 0:
                    e.cap -= d
                    self.G[e.v][e.rev].cap += d
                    return d
            i += 1
            self.iter[u] += 1
        return 0

    # find the max flow from s to v
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] == -1:
                return flow
            self.iter = [0] * self.V
            f = 0
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f

N = int(input())
A = list(map(int, input().split()))
flow = Dinic(2*N+2)
# 0..N-1: right
# N..2N-1: left
s, t = 2*N, 2*N+1
for i in range(N):
    flow.add_edge(s, i, 1)
    flow.add_edge(N+i, t, 1)
idx = defaultdict(list)
for i, a in enumerate(A):
    p = 2
    while p - a <= 10**9:
        for j in idx[p-a]:
            flow.add_edge(i, N+j, 1)
        p *= 2
    idx[a].append(i)
print(flow.max_flow(s, t))

Submission status: Wrong Answer

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

n = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = Counter(A)
ans = 0
for a in A:
  for i in range(1, 33):
    r = (1<<i) - a
    if r != a:
      if r in C and C[r] > 0:
        ans += 1
        C[r] -= 1
        break
    else:
      if C[r] >= 2:
        ans += 1
        C[r] -= 1
        break
  C[a] -= 1
print(ans)

Submission status: Wrong Answer

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

n = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = Counter(A)
ans = 0
for a in A:
  for i in range(1, 32):
    r = (1<<i) - a
    if r != a:
      if r in C and C[r] > 0:
        ans += 1
        C[r] -= 1
        break
    else:
      if C[r] >= 2:
        ans += 1
        C[r] -= 1
        break
  C[a] -= 1
print(ans)

Submission status: Wrong Answer

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

dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1
        
A.sort()
ans = 0
for i in range(N-1, -1, -1):
    if dic[A[i]] < 1:
        continue
    num = pow(2, len(bin(A[i]))-2) - A[i]
    if num in dic and dic[num] > 0:
        ans += 1
        dic[num] -= 1
        dic[A[i]] -= 1

print(ans)

Submission status: Wrong Answer

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

dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1
        
A.sort()
ans = 0
for i in range(N-1, -1, -1):
    if dic[A[i]] == 0:
        continue
    num = pow(2, len(bin(A[i]))-2) - A[i]
    if num in dic and dic[num] > 0:
        ans += 1
        dic[num] -= 1

print(ans)

Submission status: Wrong Answer

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

A.sort()
used = [0]*N

import bisect

ans = 0
for i in range(N-1, -1, -1):
    if used[i] == 1:
        continue
    for j in range(32):
        if A[i] < pow(2, j) <= 2*A[i]:
            num = pow(2, j) - A[i]
            break
    idx = bisect.bisect_left(A, num)
    while idx < i-1 and used[idx] == 1:
        idx += 1
    if A[idx] == num and idx < i:
        ans += 1
        used[idx] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    S = set(a for a in A)
    ans = 0
    while len(S) >= 2:
        x = max(S)
        S.remove(x)
        k = 1 << len(bin(x)[2:])
        if k - x in S:
            S.remove(k-x)
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

N = int(input())
A = list(map(int, input().split()))
L2 = [1]
for i in range(40):
    L2.append(L2[-1]*2)
D = defaultdict(int)
for a in A:
    D[a] += 1
A.sort(reverse=True)
res = 0
for a in A:
    if D[a] < 1:
        continue
    D[a] -= 1
    beki2 = L2[bisect.bisect_left(L2, a)]
    j = beki2 - a
    if D[j] > 0:
        D[j] -= 1
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

N = int(input())
A = list(map(int, input().split()))
L2 = [1]
for i in range(37):
    L2.append(L2[-1]*2)
D = defaultdict(int)
for a in A:
    D[a] += 1
A.sort(reverse=True)
res = 0
for a in A:
    if D[a] == 0:
        continue
    D[a] -= 1
    beki2 = L2[bisect.bisect_left(L2, a)]
    j = beki2 - a
    if D[j] > 0:
        D[j] -= 1
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

N = int(input())
A = list(map(int, input().split()))
L2= [1]
for i in range(37):
    L2.append(L2[-1]*2)
D=defaultdict(int)
for a in A:
    D[a] += 1
A.sort(reverse=True)
res = 0
for a in A:
    if D[a]==0:continue
    beki2 = L2[bisect.bisect_left(L2,a)]
    j = beki2 - a
    if D[j] > 0:
        D[j] -= 1
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=n-p
                if a in setlst[l]:
                    count+=1
                    Counerlst[l][a]-=1
                    Counerlst[l][n]-=1
                    if Counerlst[l][a]==0:
                        setlst[l].remove(a)
                    if Counerlst[l][n]==0:
                        setlst[l].remove(n)
                    break
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=n//p
                if a in setlst[l]:
                    count+=1
                    Counerlst[l][a]-=1
                    Counerlst[l][n]-=1
                    if Counerlst[l][a]==0:
                        setlst[l].remove(a)
                    if Counerlst[l][n]==0:
                        setlst[l].remove(n)
                    break
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
if __name__ == "__main__":
    N=int(input())
    lis=list(map(int,input().split()))
    lis.sort(reverse=True)
    dis={}
    for x in lis:
        if x in dis.keys():
            dis[x]=dis[x]+1
        else:
            dis[x]=1
    lis=[]
    sum=0
    for i in range(0,32):
        lis.append(pow(2,i))
    for ke,v in dis.items():
        if v<=0:
            continue
        else:
            k = 0
            while (lis[k] <= ke):
                k += 1
            r = lis[k] - ke
            if r in dis.keys() and dis[r]>0:
                if r==ke:
                    sum+=v//2
                else:
                    m=min(dis[r],v)
                    dis[r]-=m
                    sum+=m
            dis[ke]=0
    print(sum)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
if __name__ == "__main__":
    N=int(input())
    lis=list(map(int,input().split()))
    lis.sort(reverse=True)
    dis={}
    for x in lis:
        if x in dis.keys():
            dis[x]=dis[x]+1
        else:
            dis[x]=1
    lis=[]
    sum=0
    for i in range(0,32):
        lis.append(pow(2,i))
    for key,value in dis.items():
        if value<=0:
            continue
        else:
            k = 0
            while (lis[k] <= key):
                k += 1
            another = lis[k] - key
            if another in dis.keys() and dis[another]>0:
                if another==key:
                    sum+=value//2
                else:
                    m=min(dis[another],value)
                    dis[another]-=m
                    sum+=m
            dis[key]=0
    print(sum)

Submission status: Wrong Answer

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>1):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if x==y:
                ans+=mii[x]//2
            elif y<x and y in si:
                m=min(mii[x],mii[y])
                ans+=m
                mii[y]-=m
            mii[x]=0
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>1):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if x==y:
                ans+=mii[x]//2
            elif y in listb:
                m=min(mii[x],mii[y])
                ans+=m
                mii[y]-=m
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>1):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if y<=x and y in si:
                if x==y:
                    ans+=mii[x]//2
                else:
                    m=min(mii[x],mii[y])
                    ans+=m
                    mii[y]-=m
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>1):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if y in si:
                if x==y:
                    ans+=mii[x]//2
                else:
                    m=min(mii[x],mii[y])
                    ans+=m
                    mii[y]-=m
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>1):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if y in si or x==y:
                if x==y:
                    ans+=mii[x]//2
                else:
                    m=min(mii[x],mii[y])
                    ans+=m
                    mii[y]-=m
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    ans=0
    while(len(listb)>1):
        x=listb.pop()
        k=1
        while k<=x:
            k*=2
        y=k-x
        if y in si or x==y:
            if x==y:
                ans+=mii[x]//2
            else:
                m=min(mii[x],mii[y])
                ans+=m
                mii[y]-=m
    print(ans)

Submission status: Wrong Answer

Solution code:
import  math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dis={}
for x in lis:
    if x in dis.keys():
        dis[x]=dis[x]+1
    else:
        dis[x]=1
lis=[]
sum=0
for i in range(0,33):
    lis.append(pow(2,i))
for key,value in dis.items():
    if value<=0:
        continue
    else:
       k = 0
       while (lis[k] <= key):
           k += 1
       another = lis[k] - key
       if another in dis.keys() and dis[another]>0:
           if another==key:
               sum+=value//2
           else:
               m=min(dis[another],value)
               dis[another]-=m
               sum+=m
       dis[key]=0
print(sum)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))
ans=0
for some in lists:
            for j in range(1,30):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                        break
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2
                        break

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for some in lists:
            for j in range(1,30):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                        break
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2
                        break

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30-i):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                        break
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2
                        break

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30-i):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                        break
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2
                        break

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30-i):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2

print(ans)

Submission status: Wrong Answer

Solution code:
import  math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dis={}
for x in lis:
    if x in dis.keys():
        dis[x]=dis[x]+1
    else:
        dis[x]=1
lis=[]
sum=0
for i in range(0,31):
    lis.append(pow(2,i))
for key,value in dis.items():
    dis[key]=0
    if value==0:
        continue
    else:
       k = 0
       while (lis[k] <= key):
           k += 1
       another = lis[k] - key
       if another in dis.keys() :
           if another==key:
               sum+=value//2
           else:
               m=min(dis[another],value)
               dis[another]-=m
               sum+=m
print(sum)

Submission status: Wrong Answer

Solution code:
import  math
N=int(input())
lis=list(map(int,input().split()))
lis.sort(reverse=True)
dis={}
for x in lis:
    if x in dis.keys():
        dis[x]=dis[x]+1
    else:
        dis[x]=1
lis=[]
sum=0
for i in range(1,31):
    lis.append(pow(2,i))
for key,value in dis.items():
    dis[key]=0
    if value!=0:
       k = 0
       while (lis[k] <= key):
           k += 1
       another = lis[k] - key
       if another in dis.keys() :
           if another==key:
               sum+=value//2
           else:
               m=min(dis[another],value)
               dis[another]-=m
               sum+=m
print(sum)

Submission status: Wrong Answer

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

from collections import Counter 
dic=dict(Counter(lists))
counter=0
for value in dic.keys():
        for i in range(30,0,-1):
            if dic[value]>0 and ((2**i-value) in dic.keys() ) and dic[2**i-value]>0:
                if value!=2**(i-1):
                    M=min(dic[value],dic[2**i-value])
                    counter+=M
                    dic[value]-=M
                    dic[2**i-value]-=M
                elif value==2**(i-1):
                    m=dic[value]//2
                    dic[value]-=m
                    counter+=m
                if dic[value]==0:
                    continue

print(counter)