[Solution] Getting Zero solution codeforces

Getting Zero solution codeforces – Suppose you have an integer 𝑣v. In one operation, you can:

  • either set 𝑣=(𝑣+1)mod32768v=(v+1)mod32768
  • or set 𝑣=(2𝑣)mod32768v=(2⋅v)mod32768.

[Solution] Getting Zero solution codeforces

You are given 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an. What is the minimum number of operations you need to make each 𝑎𝑖ai equal to 00?

Input

The first line contains the single integer 𝑛n (1𝑛327681≤n≤32768) — the number of integers.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖<327680≤ai<32768).

Output

Print 𝑛n integers. The 𝑖i-th integer should be equal to the minimum number of operations required to make 𝑎𝑖ai equal to 00.

[Solution] Getting Zero solution codeforces

Example
input

Copy
4
19 32764 10240 49
output

Copy
14 4 4 15

Getting Zero solution codeforces

Let’s consider each 𝑎𝑖ai:

  • 𝑎1=19a1=19. You can, firstly, increase it by one to get 2020 and then multiply it by two 1313 times. You’ll get 00 in 1+13=141+13=14 steps.
  • 𝑎2=32764a2=32764. You can increase it by one 44 times: 32764327653276632767032764→32765→32766→32767→0.
  • 𝑎3=10240a3=10240. You can multiply it by two 44 times: 1024020480819216384010240→20480→8192→16384→0.
  • 𝑎4=49a4=49. You can multiply it by two 1515 times.

For Solution

Click here

Leave a Comment