1005C.md (2111B)
1 Source: https://codeforces.com/problemset/problem/1005/C 2 3 C. Summarize to the Power of Two 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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 \ne j$) such that $a_i+a_j$ is a power of two (that is, $2^d$ for some non-negative integer $d$). 22 23 For example, the following sequences are good: 24 25 * $[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$), 26 * $[1, 1, 1, 1023]$, 27 * $[7, 39, 89, 25, 89]$, 28 * $[]$. 29 30 Note that, by definition, an empty sequence (with a length of $0$) is good. 31 32 For example, the following sequences are not good: 33 34 * $[16]$ (for $a_1=16$, it is impossible to find another element $a_j$ such that their sum is a power of two), 35 * $[4, 16]$ (for $a_1=4$, it is impossible to find another element $a_j$ such that their sum is a power of two), 36 * $[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). 37 38 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. 39 40 Input 41 42 The first line contains the integer $n$ ($1 \le n \le 120000$) — the length of the given sequence. 43 44 The second line contains the sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). 45 46 Output 47 48 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. 49 50 Examples 51 52 Input 53 54 ``` 55 6 56 4 7 1 5 4 9 57 ``` 58 59 Output 60 61 ``` 62 1 63 ``` 64 65 Input 66 67 ``` 68 5 69 1 2 3 4 5 70 ``` 71 72 Output 73 74 ``` 75 2 76 ``` 77 78 Input 79 80 ``` 81 1 82 16 83 ``` 84 85 Output 86 87 ``` 88 1 89 ``` 90 91 Input 92 93 ``` 94 4 95 1 1 1 1023 96 ``` 97 98 Output 99 100 ``` 101 0 102 ``` 103 104 Note 105 106 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.