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: Runtime Error

Solution code:
def search(_a, tmp):
    while _a > 2 ** tmp:
        tmp += 1
    return tmp


n = int(input())
a = [int(i) for i in input().split()]
# a[i] + a[j] = 2^tとなる組の最大数
a.sort()
# print(a)
# diff = [search(a[i]) - a[i] for i in range(len(a))]
diff = [0 for _ in range(len(a))]
tmp = 0
for i in range(len(diff)):
    tmp = search(a[i], tmp)
    diff[i] = 2 ** tmp - a[i]
diff.sort()

i = 0
j = 0
count = 0
while i < len(a) and j < len(a):
    # print("i:{} j:{}".format(i, j))
    while diff[j] < a[i]:
        j += 1
    if a[i] == diff[j]:
        count += 1
        i += 1
        j += 1
    else:
        i += 1
print(count)

Submission status: Runtime Error

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

def bitOR(bitlist):
	N = 0
	for i in bitlist:
		N = N | (1<<i)
	return N

N = bitOR(bitlist)

s = []
bit = N
for i in range(1,N):

	push = []
	for j in range(64):
		if bit & (1<<j):
			push.append(j)
	if len(push) == 2:
		s.append( push )

	if 0 == bit: break
	bit = (bit-1) & N


re = []
for i in s:
	if float.is_integer(math.log2(sum(i))):
		for j in i:
			re.append(j)
print( len(set(re))//2 )

Submission status: Runtime Error

Solution code:
def f(N, A):
    A.sort()
    A = [a for a in map(bin, A)]
    res = 0
    for i, a in enumerate(A[:-1]):
        for b in A[i+1:]:
            tmpb = b[-len(a)+2:]
            tmpa = str(bin(~int(a, 0)))[3:]
            if tmpb == tmpa:
                res += 1
    return res

N = int(input())
A = input().split()
print(f(N, A), flush=True)

Submission status: Runtime Error

Solution code:
def calc(N):
    # 2 ** 30 > 2 * 10 ** 9
    L = list(2 ** (x+1) if 2 ** x <= N+1 else next(iter([])) for x in range(1, 31+1))
    if L == []:
        return 0
    else:
        return L[-1] - N


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

R = 0

A.sort()
A.reverse()

A_c = A.copy()

for a in A_c:
    if a in A:
        b = calc(a)
        if b in A:
            R += 1
            del A[A.index(a)]
            del A[A.index(b)]

print(R)

Submission status: Runtime Error

Solution code:
# from math import log2
from math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
avail = [True for _ in range(len(A))]

count = 0
for i in range(len(A) - 1, -1, -1):
    if not avail[i]:
        continue
    comp = getComp(A[i])
    j = bisect_left(A, comp)
    while True:
        if A[j] != comp:
            break
        if i == j or not avail[j]:
            j += 1
            continue
        avail[i] = False
        avail[j] = False
        count += 1
        break

print(count)

Submission status: Runtime Error

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

A.sort()
m = 2 ** 31
used = set()
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and mid in used):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    m //= 2
    for j in range(n):
        if j in used or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                if not A[a+1] == A[j]:
                    continue
                a += 1
            used.add(a)
            used.add(j)
            ans += 1

print(ans)

Submission status: Runtime Error

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

ans1, ans2 = 0,0

maxA = max(A)
B = [1]
t = 1
while t < maxA:
    t *= 2
    B.append(t)

d = dict()
for i in range(N):
    if A[i] in B:
        ans1 += 1
        M -= 1
    else:
        if A[i] in d:
            d[A[i]] += 1
        else:
            d[A[i]] = 1

for i in range(N):
    if A[i] not in B:
        t = 2**len(bin(A[i])[2::]) - A[i]
        if t in d:
            if d[t] > 0:
                ans2 += 1
                d[t] -= 1
                d[A[i]] -= 1

print(ans1+ans2)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
p = 1
while 2**p <=a[0]:
    p += 1
ans = 0
m =len(a)
for i in range(p,0,-1):
    j=0
    while j < m:
        k = j+1
        if k == m:
            print(ans)
            exit()
        while a[j]+a[k]>=2**i:
            if a[j]+a[k]== 2**i:
                ans += 1
                a.remove(a[k])
                a.remove(a[j])
                m -=1
                break
            else:
                k += 1
                if k ==m:
                    break
        j += 1

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
odd=[]
even=[]
for i in A:
    if i%2:
        odd.append(i)
    else:
        even.append(i)

ls=[]
for i in range(30):
    ls.append(2<<i)

ans=0
for i in range(len(odd)):
    ct=0
    for j in range(len(odd)-1):
        if i!=j:
            if odd[i]+odd[j] in ls:
                ct+=1
                tmpi=i
                tmpj=j
    if ct==1:
        odd.pop(tmpi)
        odd.pop(tmpj)
        ans+=1
for i in range(len(even)):
    ct=0
    for j in range(len(even)-1):
        if i!=j:
            if even[i]+even[j] in ls:
                ct+=1
                tmpi=i
                tmpj=j
    if ct==1:
        even.pop(tmpi)
        even.pop(tmpj)
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:


ball_num = int(input())
num_data = list(map(int, input().split()))

ans = 0

def check_beki(num1, num2):
    data = num1 + num2
    while 1:
        data1 = data % 2
        data = int(data / 2)
        if data1 == 1:
            return 0
        elif num1 + num2 >= 1 and data == 1:
            return 1

def check_ans(ans_list, tasu_flg):
    global ans
    ans_kari = 0
    for i in range(len(ans_list)):
        if check_beki(ans_list[i], 0) and tasu_flg[i] == 1:
            ans_kari += 1
    if ans_kari > ans:
        ans = ans_kari

def check(index, ans_list_ori, tasu_flg_ori):
    global ball_num, num_data
    ans_list = ans_list_ori.copy()
    tasu_flg = tasu_flg_ori.copy()

    # if len(ans_list) >= tree_num:
    #     return

    # print(check_beki(3, 5))

    if index < ball_num:
        for j in range(len(ans_list)):
            # print(ans_list[j], num_data[index])
            if check_beki(ans_list[j], num_data[index]) and tasu_flg[j] == 0:
                # print('yyy')
                ans_list[j] += num_data[index]
                tasu_flg[j] = 1
                check(index+1, ans_list, tasu_flg)
                tasu_flg[j] = 0
                ans_list[j] -= num_data[index]
            # 新しく木を使う場合
            ans_list.append(num_data[index])
            tasu_flg.append(0)
            check(index+1, ans_list, tasu_flg)
            tasu_flg.pop(-1)
            ans_list.pop(-1)
    else:
        # 以前よりも最少の気で作れたら最小値の更新
        check_ans(ans_list, tasu_flg)


def main():
    global num_data
    check(1, [num_data[0]], [0])

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def powers_of_2(n):
    while True:
        if n%2 == 0:
            n = n/2
        else:
            return False
        if n == 1:
            return True

n = int(input())
a = list(map(int, input().split()))
b = [True for _ in  range(n)]

def pair(n, a, b, _i, ans):
    list_ans = []
    for i in range(_i, n-1):
        if b[i] == False:
            continue
        for j in range(i+1, n):
            if b[j] == False:
                continue
            if powers_of_2(a[i]+a[j]):
                b[j] = False
                list_ans.append(pair(n, a, b, i+1, ans+1))
                b[j] = True
    return max(list_ans) if list_ans != [] else ans

print(pair(n, a, b, 0, 0))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

# いっこ入力
n =int(input())

answer = 0

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
a = sorted(a, reverse=True)
for i in range(31,1,-1):
    for j in a:
        b = 2**i - j
        if b in a:
            a.remove(b)
            a.remove(j)
            answer += 1

print(answer)

Submission status: Runtime Error

Solution code:
from collections import Counter
from bisect import bisect_left

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

ans = 0
C = []
for x, num in dict(Counter(A)).items():
    C.append([x, num])
C.sort()

for i in range(N):
    for t in range(33, 0, -1):
        target = 2 ** t - A[i]
        if target < 0:
            continue
        target_t = bisect_left(C, [target, 0])

        if target_t >= N:
            continue

        x, num = C[target_t]
        if x == target and num > 0 and i != target_t:
            ans += 1
            C[i][1] -= 1
            C[target_t][1] -= 1
            break

print(ans)