1661B.md (1363B)
1 Source: https://codeforces.com/problemset/problem/1661/B 2 3 B. Getting Zero 4 5 time limit per test 6 7 2 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 Suppose you have an integer $v$. In one operation, you can: 22 23 * either set $v = (v + 1) \bmod 32768$ 24 * or set $v = (2 \cdot v) \bmod 32768$. 25 26 You are given $n$ integers $a_1, a_2, \dots, a_n$. What is the minimum number of operations you need to make each $a_i$ equal to $0$? 27 28 Input 29 30 The first line contains the single integer $n$ ($1 \le n \le 32768$) — the number of integers. 31 32 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \lt 32768$). 33 34 Output 35 36 Print $n$ integers. The $i$-th integer should be equal to the minimum number of operations required to make $a_i$ equal to $0$. 37 38 Example 39 40 Input 41 42 ``` 43 4 44 19 32764 10240 49 45 ``` 46 47 Output 48 49 ``` 50 14 4 4 15 51 ``` 52 53 Note 54 55 Let's consider each $a_i$: 56 57 * $a_1 = 19$. You can, firstly, increase it by one to get $20$ and then multiply it by two $13$ times. You'll get $0$ in $1 + 13 = 14$ steps. 58 * $a_2 = 32764$. You can increase it by one $4$ times: $32764 \rightarrow 32765 \rightarrow 32766 \rightarrow 32767 \rightarrow 0$. 59 * $a_3 = 10240$. You can multiply it by two $4$ times: $10240 \rightarrow 20480 \rightarrow 8192 \rightarrow 16384 \rightarrow 0$. 60 * $a_4 = 49$. You can multiply it by two $15$ times.