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:
from collections import defaultdict as dd
from collections import Counter
from pprint import pprint as pp

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

def is_beki(n):
  return (n & (n-1)) == 0

ret = 0

for i in range(1, N):
  a = A[i]
  max_b = 0
  max_j = 0
  for j in range(i):
    b = A[j]
    if max_b >= b:
      continue
    if is_beki(a+b):
      max_b = b
      max_j = j
  if max_b != 0:
    A[max_j] = 0
    A[i] = 0
    ret += 1

print(ret)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import random;
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
# N = 2*10**5
# A = [random.randint(1,10**9) for _ in range(N)]
dp = defaultdict(int)

ans = 0
for a in A:
    tmp = 2
    for _ in range(30):
        if tmp >= a:
            ans += dp[tmp - a]
        tmp *= 2
    tmp = 2
    for _ in range(30):
        if tmp >= a:
            dp[tmp - a] += 1
        tmp *= 2
        
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[2**i for i in range(1,31)]
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
      r-=1
    elif A[l]+A[r]<t:
      l+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import copy
N = int(input())
a = list(map(int, input().split()))
a.sort()

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

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


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

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

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

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










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

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


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

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxa=max(a)
m=len(bin(maxa))-2
x=[[] for _ in range(m)]
for i in range(n):
    x[len(bin(a[i]))-3].append(a[i])
#print(x)
y=[]
for i in range(m):
    ti=m-1-i
    tx=[]
    for j in range(len(x[ti])):
        tj=len(x[ti])-1-j
        tx=2**(len(bin(x[ti][tj]))-2)-x[ti][tj]
        tk=len(bin(tx))-3
        #print(tx,x[ti][tj])
        if x[ti][tj]==tx:
            y.append(tx)
            continue
        
        tz=bisect.bisect_left(x[tk],tx)
        if tz<len(x[tk]) and tx==x[tk][tz]:
            del x[tk][tz]
        else:
            y.append(x[ti][tj])
y.sort()
ans=0
z=[2**i for i in range(32)]
y.append(0)
#print(y)
j=False
for i in range(len(y)-1):
    if y[i] in z:
        if y[i]==y[i+1]:
            if j:
                j=False
            else:
                j=True
        elif j is False:
            ans+=1
    else:
        ans+=1
ans=(n-ans)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_right(A, t)
    if i >= n:
        return False

    while t == A[i]:
        if i not in already:
            already.add(i)
            return True
        i -= 1
        if i < 0:
            return False

    return False

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        if is_in(t - a, n):
            res += 1
            break
        t >>= 1

print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import deque

N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
lctr = sorted(list(ctr.items()))
order = {k:i for i,(k,_) in enumerate(lctr)}

bekis = [2]
while bekis[-1] < 2*10**9:
    bekis.append(bekis[-1] * 2)

es = [[] for i in range(len(lctr)*2+2)] # [[to1,cap1,rev1], ...]

def add_edge(fr,to,cap):
    es[fr].append([to,cap,len(es[to])])
    es[to].append([fr,cap,len(es[fr])-1])

for i in range(len(lctr)):
    add_edge(0, 1+i, lctr[i][1])
    add_edge(len(lctr)*2+1, 1+i+len(lctr), lctr[i][1])
for i,(k,v) in enumerate(lctr):
    for beki in bekis:
        if k < beki-k and beki-k in ctr:
            j = order[beki-k]
            add_edge(1+i, 1+len(lctr)+j, min(v,ctr[beki-k]))
b = 1
while b < 2*10**9:
    if b in ctr:
        i = order[b]
        add_edge(1+i, 1+len(lctr)+i, ctr[b]//2)
    b *= 2

INF = float('inf')
level = [0] * (len(lctr)*2+2)
iters = [0] * (len(lctr)*2+2)

def dinic_max_flow(s,t):
    global iters

    def _bfs(s):
        global level
        level = [-1] * (len(lctr)*2+2)
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to,cap,rev in es[v]:
                if cap > 0 and level[to] < 0:
                    level[to] = level[v] + 1
                    q.append(to)

    def _dfs(v,t,f):
        if v == t: return f
        for i in range(iters[v],len(es[v])):
            iters[v] += 1
            to,cap,rev = es[v][i]
            if es[v][i][1] > 0 and level[v] < level[to]:
                d = _dfs(to,t,min(f,es[v][i][1]))
                if d > 0:
                    es[v][i][1] -= d #cap
                    es[to][rev][1] += d
                    return d
        return 0

    flow = 0
    while True:
        _bfs(s)
        if level[t] < 0: return flow
        iters = [0] * (len(lctr)*2+2)
        f = 0
        while True:
            f = _dfs(s,t,INF)
            if f <= 0: break
            flow += f

print(dinic_max_flow(0,len(lctr)*2+1))

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math

N=int(input())

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

answer=0
A.sort(reverse=True)

Amax=A[0]
limit=1
while(True):
  if limit>Amax:
    break;
  limit*=2

Acounter=Counter(A)
print(Acounter)

while(limit!=1):
  eraserlist=[]
  for number,count in Acounter.items():
    if limit-number in Acounter.keys():
      if number==limit-number:
        dec=math.floor(Acounter[number]/2)
        Acounter[number]-=dec*2
      else:
        dec=min(Acounter[number],Acounter[limit-number])
        Acounter[number]-=dec
        Acounter[limit-number]-=dec
        if Acounter[limit-number]==0:
          eraserlist.append(limit-number)
      if Acounter[number]==0:
        eraserlist.append(number)
      answer+=dec
    if number>=limit/2:
      eraserlist.append(number)
  for i in range(len(eraserlist)):
    if eraserlist[i] in Acounter.keys():
      Acounter.pop(eraserlist[i])
  limit=int(limit/2)
print(answer)
print(Acounter)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))

odd = [A[i] for i in range(N) if A[i]%2 != 0 ]
even = list(set(A)-set(odd))

odd.sort(reverse=True)
even.sort(reverse=True)

count = 0
for i in range(len(odd)):
    for j in odd[i+1:]:
        if float.is_integer(np.log2(odd[i] + j)):
            odd.remove(j)
            count += 1
            break

for i in range(len(even)):
    for j in even[i+1:]:
        if float.is_integer(np.log2(even[i] + j)):
            even.remove(j)
            count += 1
            break

print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 15 21:15:13 2018
AGC029B
@author: maezawa
"""
import collections

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
c = collections.Counter(a)

beki2 = [2**i for i in range(1,31)]

cnt = 0

for i in a:
    for j in beki2:
        if j-i > amax:
            break
        if j-i in c:
            if j-i == i and c[j-i] == 1:
                continue
            cnt += 1
            #print(i,j-i)

print(cnt//2)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

count = Counter(aaa)
sk = sorted(count.keys())
rd = {a: i for i, a in enumerate(sk)}
lc = len(count)
ma = max(count)
ma2 = 1 << (ma.bit_length() + 2)

mf = Dinic(2 * lc + 2)

for i in range(lc):
    a = sk[i]
    cnt = count[a]
    li = i + 1
    k = 2
    b = k - a
    while b <= ma:
        if b > 0 and b in count:
            if a != b or cnt > 1:
                mf.add_link(li, lc + rd[b] + 1, cnt)
        k <<= 1
        b = k - a
    mf.add_link(0, li, cnt)
    mf.add_link(lc + li, 2 * lc + 1, cnt)

# print(*mf.links, sep='\n')

print(mf.max_flow(0, 2 * lc + 1) // 2)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
c = collections.Counter(a)

beki2 = [2**i for i in range(1,31)]

cnt = 0

for i in a:
    for j in beki2:
        if j-i > amax:
            break
        if j-i in c:
            if j-i == i and c[j-i] == 1:
                continue
            cnt += 1
            print(i,j-i)

print(cnt//2)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
n = int(input())
evens, odds = defaultdict(int), defaultdict(int)
for x in input().split():
    x = int(x)
    if x % 2 == 0:
        evens[x] = 1
    else:
        odds[x] = 1

def ok(x, y):
    if math.log(x+y, 2).is_integer():
        return True
    return False

def search(dic, ls, evens, count, even_max):
    for i, x in enumerate(ls):
        if dic[x] == 1:
            for j, y in enumerate(ls[i+1:]):
                if dic[y] == 1 and ok(x, y):
                    count += 1
                    dic[x] = dic[y] = 2
                    for k in range(even_max):
                        a = x * (2 ** k)
                        b = y * (2 ** k)
                        if max(a, b) > even_max:
                            break
                        if evens[a] == evens[b] == 1:
                            evens[a] = evens[b] = 2
                            count += 1
                    break
    return count



even_max = max(evens.keys())
count = 0
odds_v = list(odds.keys())
count = search(odds, odds_v, evens, count, even_max)
evens_v = [k for k,v in evens.items() if v == 1]
count = search(evens, evens_v, evens, count, even_max)

print(count)

Submission status: Wrong Answer

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

ans = 0
pwtwo = [2**i for i in range(1, 31)]
pn = [0 for _ in range(n)]
ok = []
for i in range(n):
    for j in range(i+1, n):
        if (a[i]+a[j]) in pwtwo:
            ok.append((i, j))
            pn[i] += 1
            pn[j] += 1
while 1 in pn:
    i = pn.index(1)
    for j in range(n):
        if i in ok[j]:
            p, q = ok[j]
            pn[p] = 0
            pn[q] = 0
            break
    ans += 1

ans += sum(x >= 2 for x in pn) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a


import bisect

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


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

A.sort()
ma = A[-1]

uf = UnionFind(N)

for i, ai in enumerate(A):
    for p2i in p2:
        cand = p2i - ai
        if cand < ai:
            continue
        if cand > ma:
            break
        j = bisect.bisect_left(A, cand, lo=i+1)
        if j != N and A[j] == cand:
            uf.union(i, j)

count = 0
for t in uf.subsetall():
    l, r = t
    count += r // 2
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

count = Counter(aaa)
sk = sorted(count.keys())
rd = {a: i for i, a in enumerate(sk)}
lc = len(count)
ma = max(count)
ma2 = 1 << (ma.bit_length() + 2)

mf = Dinic(2 * lc + 2)

for i in range(lc):
    a = sk[i]
    cnt = count[a]
    li = i + 1
    k = 2
    b = k - a
    while b < ma:
        if b > 0 and b in count:
            if a != b or cnt > 1:
                mf.add_link(li, lc + rd[b] + 1, cnt)
        k <<= 1
        b = k - a
    mf.add_link(0, li, cnt)
    mf.add_link(lc + li, 2 * lc + 1, cnt)

# print(*mf.links, sep='\n')

print(mf.max_flow(0, 2 * lc + 1) // 2)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def main():
    powerof2 = set() 
    for i in range(32):
        powerof2.add(2 ** i)

    n = int(input())
    a = list(enumerate(map(lambda x: int(x), input().split(' '))))
    sorted_a = list(reversed(sorted(a, key=lambda x: x[1])))

    anti = set()
    count = 0
    for x, y in combinations(sorted_a, 2):
        if (x in anti) or (y in anti):
            break
        if x[1] + y[1] in powerof2:
            anti.add(x)
            anti.add(y)
            count += 1
    print(count)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
S = np.sort(list(map(int, input().split())))
pair = {}
for x in [2**i for i in range(32)][1:]:
  for i in range(N):
    a = S[i]
    for jj in range(N):
      j = N-jj-1
      if i == j:
        continue
      b = S[j]
      if(a+b==x):
        if i in pair:
          pair[i].append(j)
        else:
          pair[i] = [j]
      if a+b < x:
        break
    if a > x:
      break

match = -1 * np.ones(N, dtype=int)
used = np.zeros(N)

def dfs(v):
  used[v] = True
  if v in pair:
    for u in pair[v]:
      w = match[u]
      if w < 0:
        match[v] = u
        match[u] = v
        return True
      if used[w] == 0 and dfs(w):
        match[v] = u
        match[u] = v
        return True

  return False

res = 0
for v in range(N):
  if (match[v] < 0):
    used = np.zeros(N)
    if (dfs(v)):
      res += 1
print(res)

Submission status: Wrong Answer

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

M=max(a)
for i in range(100):
  if 2**i>M:
    x=i
    break
L=[]
for j in range(2**x-1):
  L.append(0)

for j2 in range(n):
  L[a[j2]-1]+=1

for k in range(x,1,-1):
  l1=L[0:2**(k-1)-1]
  l2=L[2**(k-1):2**k]
  l2.reverse()
  ct+=int(L[2**(k-1)-1]/2)
  for m in range(len(l1)):
    if l1[m]>=1 and l2[m]>=1:
      ct+=min(l1[m],l2[m])
      l1[m]-=min(l1[m],l2[m])
      l2[m]-=min(l1[m],l2[m])
  L=l1
ct+=int(L[0]/2)
print(ct)
print(x)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
T=[2**i for i in range(1,31)]
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
      l+=1
      r-=1
    elif A[l]+A[r]<t:
        l+=1
print(ans)

Submission status: Wrong Answer

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

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

pairCounter=0
for i in range(N):
  if A[i] <1:
    continue
  for j in range(N -i -1):
    if A[j+i +1] < 1:
      continue
    wa = A[i] + A[j+i +1]
    for b in range(9):
      if 2**b & wa == wa:
        A[i]=-1
        A[j+i +1]=-1
        pairCounter+=1

print(pairCounter)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import Counter
from pprint import pprint as pp

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

def is_beki(n):
  return (n & (n-1)) == 0

ret = 0

for i in range(1, N):
  a = A[i]
  max_b = 0
  max_j = 0
  for j, b in enumerate(A[:i]):
    if max_b >= b:
      continue
    if is_beki(a+b):
      max_b = b
      max_j = j
  if max_b != 0:
    A[max_j] = 0
    A[i] = 0
    ret += 1

print(ret)

Submission status: Wrong Answer

Solution code:
def f(N, A):
    A.sort()
    #A = [a for a in map(bin, A)]
    used = [False] * N
    res = 0
    for i, a in enumerate(A[:-1]):
        if used[i]: continue
        for j, b in list(enumerate(A[i+1:][::-1])):
            if used[N-j-1]: continue
            if all([x == "0" for x in bin(a+b)[3:]]):
                res += 1
                used[i] = True
                used[N-j-1] = True
                break
    return res
 
N = int(input())
A = list(map(int, input().split()))
print(f(N, A), flush=True)

Submission status: Wrong Answer

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] and i!=b and x[b]: x[b],ans = 0,ans+1
print(ans)

Submission status: Wrong Answer

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

ans = 0
pwtwo = [2**i for i in range(1, 31)]
pn = [0 for _ in range(n)]
ok = []
for i in range(n):
    for j in range(i+1, n):
        if (a[i]+a[j]) in pwtwo:
            ok.append((i, j))
            pn[i] += 1
            pn[j] += 1
while 1 in pn:
    i = pn.index(1)
    for j in range(n):
        if i in ok[j]:
            p, q = ok[j]
            pn[p] = 0
            pn[q] = 0
            del ok[j]
            break
    ans += 1

ans += sum(x >= 2 for x in pn)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

P2=[]
for i in range(1,32):
  P2.append(2**(32-i))
  
def solve():
  a=A.pop()
  l=len(A)
  for i in range(31):
    if a > P2[i]:
      return False
    else:
      cnt=P2[i]-a
      b=bisect.bisect_left(A,cnt)
      if b != l and A[b]== cnt:
        A.pop(b)
        return True

ans=0
for i in range(N):
  if len(A) < i:
    break
  else:
    if solve():
      ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict, deque
N = int(input())
tmp = list(map(int, input().split()))
An = deque()
for a in tmp:
    An.append(a)

maxA = max(tmp)

t2 = [2**i for i in range(32) if 2**i <= maxA]
t2.reverse()

ans = 0
for t in t2:
    tmp_dict = defaultdict(list)
    for A in An:
        tmp_dict[A%t].append(A)

    tmp = 0
    for k,v in list(tmp_dict.items()):
        if k == 0 or k == t:
            m = len(v) // 2
        else:
            m = min([len(v), len(tmp_dict[t-k])])
        if m > 0:
            tmp += m
            for l in v + tmp_dict[t-k]:
                try:
                    An.remove(l)
                except Exception:
                    pass
    ans += tmp//2

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
# N = int(input())
# A = list(map(int, input().split()))
A = [3, 11, 14, 5, 13]

A = np.array(A)
ax, ay = np.meshgrid(A, A)
AA = ax + ay
triAA = np.triu(AA, k=1)
# print(triAA.dtype)
# triAA = triAA.ravel()
# print(triAA)
# np.where(triAA)
row_bool = np.array([False]*len(A))
# print(row_bool)
powers = [int(2**i) for i in range(1, 33)]
for p in powers:
    # print(row_bool)
    row_bool = np.logical_or(row_bool, np.any(triAA == p, axis=0))
    # total += np.any(triAA == p, axis=0).sum()
print(row_bool.sum())
# print(triAA in (1, 2))

Submission status: Wrong Answer

Solution code:
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()

def is_in(t, n):
    i = bisect.bisect_left(A, t)
    if i < n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)

Submission status: Wrong Answer

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] and i!=b: x[b],ans = 0,ans+1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if N == 1:
    print(1)
    exit(0)

ans = 1
mx = ( 1 , A[0] )
for i in range(N-1):
    if A[i+1] <= A[i]:
        v = mx[0] // pow(ans,A[i] - A[i+1])
        if v == (ans ** A[i+1]):
            ans += 1
        mx = (v+1,A[i+1])
    else:
        mx = ( mx[0] * pow(ans,(A[i+1] - A[i])) , A[i+1] )
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = 0
pwtwo = [2**i for i in range(1, 31)]
pn = [0 for _ in range(n)]
ok = []
for i in range(n):
    for j in range(i+1, n):
        if (a[i]+a[j]) in pwtwo:
            ok.append((i, j))
            pn[i] += 1
            pn[j] += 1
print(pn, ok)
while 1 in pn:
    i = pn.index(1)
    for j in range(n):
        if i in ok[j]:
            p, q = ok[j]
            pn[p] = 0
            pn[q] = 0
            del ok[j]
            break
    ans += 1

ans += sum(x >= 2 for x in pn)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

a.sort()
M=a[-1]*2


powers=2
count=0
for i in range(n):
    while powers<a[i]:
        want=powers*2-a[i]
        l=bisect.bisect_left(a,want)        
        r=bisect.bisect_right(a,want)
        if l<n and a[l]==want:
            count+=(r-l)
        powers*=2

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

beki2 = [2**i for i in range(31)]
N = int(input())
A = list(map(int, input().split()))

ct = Counter(A)
ans = 0
for i in sorted(ct.keys()):
  numi = ct[i]
  for j in beki2:
    k = j - i
    if i != k:
      if k in ct:
        numk = ct[k]
        m = numi if numi < numk else numk
        ans += m
        ct[i] -= m
        ct[k] -= m

for j in beki2:
  if j in ct:
    ans += ct[j] // 2

print(ans)

Submission status: Wrong Answer

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

count = 0
done_index = []
for i_index, i in enumerate(A):
    for j_index, j in enumerate(A):
        if i_index == j_index or i_index in done_index or j_index in done_index:
            continue
        if not((i + j) & ((i + j) - 1)):
            count += 1
            done_index.append(i_index)
            done_index.append(j_index)
            break

print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

dp = defaultdict(int)

ans = 0
for a in A:
    tmp = 2
    for i in range(1,31):
        if tmp >= a:
            ans += dp[tmp - a]
        tmp *= 2
    tmp = 2
    for i in range(1,31):
        if tmp >= a:
            dp[tmp - a] += 1
        tmp *= 2
        
print(ans)