526互联

Getting Zero(Bfs)

发布时间 2023-06-21 13:07:56作者: o-Sakurajimamai-o
Getting Zero
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Suppose you have an integer v. In one operation, you can:

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

You are given n integers a1,a2,…,an What is the minimum number of operations you need to make each ai equal to 0?

Input

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

The second line contains n integers a1,a2,… (0≤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 0.

Example
input Copy
4
19 32764 10240 49
output Copy
14 4 4 15
Note

Let's consider each ai:

  • a1=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=14steps.
  • a2=32764. You can increase it by one 44 times: 32764→32765→32766→32767→0.
  • a3=10240. You can multiply it by two 44 times: 10240→20480→8192→16384→0
  • a4=49. You can multiply it by two 15 times.

       :

//Getting Zero:https://www.luogu.com.cn/problem/CF1661B
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=32768;
string s;
int n,t,a[N],f[N],res,num,ans;
bool vis[N];
struct node
{
    int x,step;
};
int bfs(int u)
{
    queue<node>que;
    node str;
    str.x=u,str.step=0;
    que.push(str);
    while(!que.empty()){
        node now=que.front();
        que.pop();
        if(now.x==0) return now.step;
        if(vis[now.x]) continue;
        vis[now.x]=true;
        node next;
        next.x=(now.x+1)%mod,next.step=now.step+1;
        que.push(next);
        next.x=(now.x*2)%mod,next.step=now.step+1;
        que.push(next);
    }
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        cout<<bfs(n)<<" ";
        memset(vis,false,sizeof vis);
    }
    return 0;
}