codeforces-scrape

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

2118C.md (1852B)


      1 Source: https://codeforces.com/problemset/problem/2118/C
      2 
      3 C. Make It Beautiful
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ of $n$ integers. We define the $\text{beauty}$ of a number $x$ to be the number of $1$ bits in its binary representation. We define the beauty of an array to be the sum of beauties of the numbers it contains.
     22 
     23 In one operation, you can select an index $i$ $(1 \le i \le n)$ and increase $a_i$ by $1$.
     24 
     25 Find the maximum beauty of the array after doing at most $k$ operations.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.
     30 
     31 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 5000$, $0 \le k \le 10^{18}$) — the length of the array and the maximal number of operations.
     32 
     33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($0 \le a_i \le 10^9$) —denoting the array $a$.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.
     36 
     37 Output
     38 
     39 For each test case, output a single integer, the maximum beauty after at most $k$ operations.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 
     48 5 2
     49 
     50 0 1 7 2 4
     51 
     52 5 3
     53 
     54 0 1 7 2 4
     55 
     56 1 1
     57 
     58 3
     59 
     60 3 0
     61 
     62 2 0 3
     63 
     64 1 100000000000
     65 
     66 0
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 8
     73 9
     74 2
     75 3
     76 36
     77 ```
     78 
     79 Note
     80 
     81 In the first test case, $a = [0, 1, 7, 2, 4]$.
     82 
     83 * apply the first operation at $i = 1$, the new array is $a = [1, 1, 7, 2, 4]$
     84 * apply the second operation at $i = 4$, the new array is $a = [1, 1, 7, 3, 4]$
     85 
     86 The beauty of this array is $1 + 1 + 3 + 2 + 1 = 8$. One of the other valid solutions with the same beauty is $[0, 1, 7, 3, 5]$.
     87 
     88 In the third test case, $a = [3]$. Since you are not required to use exactly $k$ operations, it is optimal to do none.