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?
InputThe 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).
OutputPrint n integers. The i-th integer should be equal to the minimum number of operations required to make ai equal to 0.
Example input Copy4 19 32764 10240 49output Copy
14 4 4 15Note
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; }
标签:integers,Getting,int,step,next,Bfs,Zero,que,now From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17495999.html