codeforces-scrape

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

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.