EduCfRound82 A~D

A Erasing Zeroes standard input/output 1 s, 256 MB Submit Add to favourites x9251

　　把第一个1前面的0 和最后一个1的0 从0的总数减去即可
B National Project standard input/output 2 s, 256 MB Submit Add to favourites x5533

　　 (make sure that at least half of the highway will have high-quality pavement. ) x = ((n+1)/2), needG = ((x+g-1)/g * (g+b)), and if some highway is still not repaired, answer should add it，

然后也可以二分查找 needG
C Perfect Keyboard standard input/output2 s, 256 MB Submit Add to favourites x3592

　　jia将每个字母变成一个顶点然后建边如果有个顶点边大于三条则无解，否则就从只有一条边的定点开始 dfs 遍历将顶点加入ans字符串，如果结束后 ans长度 != 26 则无解

D Fill The Bag standard input/output 2 s, 256 MB Submit Add to favourites x1423

　　//r如果 sum（a） < n 无解

　　//只有当n 的某位进制没有需要前位拆分时才会造成贡献
　　//例如 n = 9 a={ 8 8 8 8} ,so 8 -> 4 -> 2 -> 1 ans+=3;
　　//如果低位的 i 值没有贡献可以向前进位

Builtin functions of GCC compiler

　　_builtin_popcount(x): This function is used to count the number of one’s(set bits) in an integer.

　　_builtin_parity(x): This function is used to check the parity of a number. This function returns true(1) if the number has odd parity else it returns false(0) for even parity.

　　__builtin_clz(x): This function is used to count the leading zeros of the integer. Note : clz = count leading zero’s

　　__builtin_ctz(x): This function is used to count the trailing zeros of the given integer. Note : ctz = count trailing zeros.

#include <bits/stdc++.h> //cf ER82
using namespace std;
#define ll long long
#define _for(i,a,b) for(int i = (a); i < (b); i++) 
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)
#define sz(v) ((int) (v).size())

void taskA(){
    int t;cin >> t;
    while(t--) {
        string s;
        cin >> s;
        int cnt = 0, f = 0;
        _for(i,0,s.size()) {
            if(f && s[i] == '0') cnt++;
            if(s[i]=='1') f = 1;            
        }
        int cnt1 = 0;
        for(int i = s.size()-1; i >= 0; i--) {
            if(s[i] == '0') cnt1++;
            else break;
        }
        if(cnt) cnt -= cnt1;
        cout << cnt << "
"; 
    }
    return;
}

void taskB(){
    int t; cin >> t;
    while(t--) {
        ll n,g,b;
        cin >> n >> g >> b;
        if(g >= n) cout << n << "
";
        else{
            ll x = (n+1)/2;
            ll y = (x+g-1)/g;
            ll ans = (y-1)*(g+b)+(x-(y-1)*g);
            ll x1 = n/2-(y-1)*b;
            //cout << "x = " << x << "  y = " << y << " ans = " << ans << "  x1= " << x1 << "
";
            if(x1 > 0) ans += x1;
            cout << ans << "
";
        }
    }
    return;
}

void taskB1() {
    int t; cin >> t;
    while(t--) {
        ll n,g,b; cin >> n >> g >> b;
        ll g1 = (n+1)/2, l = n, r = 1e18, ans = n;
        while(l <= r) {
            ll mid = (l+r)/2;
            ll gd = mid/(g+b)*g + min(mid%(g+b), g);
            if(gd >= g1) ans = mid, r = mid-1;
            else l = mid+1;
        }
        cout << ans << "
";
    }
    return;
}

void taskC1(){
    int t; cin >> t;
    while(t--) {
        string s; cin >> s;
        vector<bool> used(26, false);
        string t(1, s[0]); used[s[0]-'a'] = true;
        int n = s.size(), f = 0, pos = 0;
        _for(i,1,n) {
            if(used[s[i]-'a']) {
                if(pos && t[pos-1] == s[i]) pos--;
                else if(pos+1 < sz(t) && t[pos+1] == s[i]) pos++;
                else { cout << "NO
"; f = 1; break; }
            } else {
                if(!pos) t = s[i]+t;
                else if(pos == sz(t)-1) t += s[i], pos++;
                else { cout << "NO
"; f = 1; break; }
            }
            used[s[i]-'a'] = true;
        }
        if(!f) {
            cout << "YES
";
            _for(i,0,26) if(!used[i]) t += char(i+'a');
            cout << t << "
";
        }
    }
    return;
}

const int N = 27;
int vis[N];
string ans;
vector<int> g[N];
void dfs(int x) {
    vis[x] = 1; ans += char(x+'a');
    for(int i = 0; i < g[x].size(); i++) if(!vis[g[x][i]]) dfs(g[x][i]);
    return;
}
void taskC() {
    int t; cin >> t;
    while(t--) {
        string s; cin >> s;
        int n = s.size();

        ans = ""; _for(i,0,26) vis[i] = 0, g[i].clear();

        set<pair<int, int> >se;
        _for(i,1,n) {
            int a = s[i]-'a', b = s[i-1]-'a';
            if(a > b) swap(a, b);
            if(!se.count({a,b}))
            {
                g[a].push_back(b); g[b].push_back(a);
                se.insert({a,b});
            }
        }
        int f = 0;
        _for(i,0,26) 
        {
            if(g[i].size() > 2) {f = 1; break; }
            if(!vis[i] && g[i].size() < 2) dfs(i);            
        } 
        if(!f && ans.size() == 26) cout << "YES
" << ans << "
";
        else cout << "NO
";
    }
    return;
}

void taskD(){
    int t; cin >> t;
    while(t--) {
        ll n,m; cin >> n >> m;
        vector<int> a(61, 0);
        ll sum = 0;
        _for(i,0,m) {
            int x;
            cin >> x, sum += x;
            int pos = 0;
            while(x > 1) {x /= 2; pos++;};
            //cout << pos << " = pos
";
            //++a[31-__builtin_clz(a)];//求 a 的二进制表示的 i a=2^i
            a[pos]++;
        }
        if(sum < n) cout << "-1
"; 
        else {
            int ans = 0;
            _for(i,0,32) {
                if((n>>i) & 1) {
                    if(!a[i]) {
                        int j = i+1;
                        while(!a[j]) j++;
                        a[j]--;
                        while(i <= --j) a[j]++, ans++;
                        a[i]++;
                    }
                    a[i]--;
                }
                a[i+1] += a[i]/2; //can be put in box directly
            }
            cout << ans << "
";
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    //taskA();
    //taskB();
    //taskC();
    taskD();
    return 0;
}