codeforces-scrape

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

2231C.md (2533B)


      1 Source: https://codeforces.com/problemset/problem/2231/C
      2 
      3 C. Chipmunk Theo and Equality
      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 While exploring the depths of the Internet, Theodore the chipmunk found a very interesting sequence of positive integers and decided to play with it.
     22 
     23 In one operation, he chooses an element of the sequence and performs the following action:
     24 
     25 * If the chosen element is even, he divides it by 2.
     26 * If the chosen element is odd, he increases it by 1.
     27 
     28 Theo really loves equality, so he wants to make all numbers in the sequence equal (otherwise, some numbers might feel offended). Since he needs to plan his lunch time, help him determine the minimum number of operations required to make all numbers equal.
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     33 
     34 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the sequence.
     35 
     36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the sequence.
     37 
     38 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     39 
     40 Output
     41 
     42 For each test case, output a single integer — the minimum number of operations Theo needs to make all numbers in the sequence equal.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 3
     52 
     53 3 2 4
     54 
     55 7
     56 
     57 3 6 7 16 8 8 7
     58 
     59 3
     60 
     61 1 4 2
     62 
     63 5
     64 
     65 10 10 10 10 10
     66 
     67 6
     68 
     69 1 1 3 1 1 1
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 3
     76 
     77 11
     78 
     79 2
     80 
     81 0
     82 
     83 3
     84 ```
     85 
     86 Note
     87 
     88 In the first test case, we have a sequence: $[3, 2, 4]$
     89 
     90 One possible sequence of operations: $$ [\textbf{3}, 2, 4] \rightarrow [\textbf{4}, 2, 4] \rightarrow [2, 2, \textbf{4}] \rightarrow [2, 2, 2] $$ (Operations are performed on numbers shown in bold.)
     91 
     92 In the second test case, the sequence is: $[3, 6, 7, 16, 8, 8, 7]$
     93 
     94 Possible operations:
     95 
     96 * Perform the operation once on the 1st element: $3 \rightarrow 4$
     97 * Perform the operation twice on the 2nd element: $6 \rightarrow 3 \rightarrow 4$
     98 * Perform the operation twice on the 4th element: $7 \rightarrow 8 \rightarrow 4$
     99 * Perform the operation twice on the 5th element: $16 \rightarrow 8 \rightarrow 4$
    100 * Perform the operation once on the 6th element: $8 \rightarrow 4$
    101 * Perform the operation once on the 7th element: $8 \rightarrow 4$
    102 * Perform the operation twice on the 8th element: $7 \rightarrow 8 \rightarrow 4$
    103 
    104 After these $11$ operations, all elements become $4$.