Codeforces Round #496 (Div. 3) C. Summarize to the Power of Two（打表暴力）

本文主要是介绍Codeforces Round #496 (Div. 3) C. Summarize to the Power of Two（打表暴力），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A sequence $a_{1}, a_{2}, \dots, a_{n}$ is called good if, for each element $a_{i}$ , there exists an element $a_{j}$ ( $i \neq j$ ) such that $a_{i} + a_{j}$ is a power of two (that is, $2^{d}$ for some non-negative integer $d$ ).

For example, the following sequences are good:

$[5, 3, 11]$ (for example, for $a_{1} = 5$ we can choose $a_{2} = 3$ . Note that their sum is a power of two. Similarly, such an element can be found for $a_{2}$ and $a_{3}$ ),
$[1, 1, 1, 1023]$ ,
$[7, 39, 89, 25, 89]$ ,
$[]$ .

Note that, by definition, an empty sequence (with a length of $0$ ) is good.

For example, the following sequences are not good:

$[16]$ (for $a_{1} = 16$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two),
$[4, 16]$ (for $a_{1} = 4$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two),
$[1, 3, 2, 8, 8, 8]$ (for $a_{3} = 2$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two).

You are given a sequence $a_{1}, a_{2}, \dots, a_{n}$ . What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.

Input

The first line contains the integer $n$ ( $1 \leq n \leq 120000$ ) — the length of the given sequence.

The second line contains the sequence of integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Output

Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all $n$ elements, make it empty, and thus get a good sequence.

Examples 
input Copy 
6
4 7 1 5 4 9
output Copy 
1
input Copy 
5
1 2 3 4 5
output Copy 
2
input Copy 
1
16
output Copy 
1
input Copy 
4
1 1 1 1023
output Copy 
0

Note

In the first example, it is enough to delete one element $a_{4} = 5$ . The remaining elements form the sequence $[4, 7, 1, 4, 9]$ , which is good.

题意：给你n个数，这些数中任意两个数的和（下标不能相等），如果是2的幂次方就满足条件，输出不满足数的个数

思路：先打表找出（1~30）2的幂次方，然后把每一个数都放入map里面（去重并统计个数），然后两层for枚举，还要注意类似2+2符合条件，但只有一个2也是不符合的。

ACDAIMA：

#include <bits/stdc++.h>
using namespace std;
int a[120];
map <int,int> mp;
int main()
{int n, x;for(int i = 1; i < 31; i++) a[i] = 1 << i;while(~scanf("%d",&n)){mp.clear();for(int i = 0; i < n; i++){scanf("%d", &x);mp[x]++;}int ans = 0;for(auto i: mp){int t = i.first;bool flag = false;for(int j = 1; j < 31; j++){if(a[j] - t == t){if(mp.count(t) && mp[t] > 1) { flag = true; break; }}else if(mp.count(a[j]-t)) { flag = true; break; }}if(!flag) ans += i.second;}printf("%d\n",ans);}}

这篇关于Codeforces Round #496 (Div. 3) C. Summarize to the Power of Two（打表暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！