codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.