I have a really dumb and edging solution. We see it is monotonic for if it's possible at length x. We may also assume k is less than 2^63, prob 1e18 Meaning to check for one we can do 63*n and log_2 64 is 6 so by binsearch we can do 63*6*n, assuming n is 2e5 we end at around 7e7 or 8e7, which is sorta edging but should pass

Tldr: binsearch on bf

greedy method? idk if my smooth buttery brain correct

go through the string from right to left, try to include as many characters as possible:

include all '0's unconditionally

include a '1' only if adding 2^position still keeps total value ≤ k

also we need to keep track of the total value of the bits included and the number of bits included

when including any new '1' that would push us over k, stop adding 1s, but any remaining '0's from the left can still be included

yeah this is just my idea

Greedy should work. An optimal subsequence can be the following: 1) Include all 0's in the string 2) Add 1's starting from the right of the string as long as we do not exceed k. Proving 1) is easy too: => If say an optimal subsequence does not contain the 0 at position i of the string, there are 2 cases: Case 1 : we do not include any 1 to the left of position i in our answer. Here we can include the 0 at i without changing the value as these are just leading zeroes. Case 2 : there is a 1 to the left of i. We can remove this 1 and add 0 at i without changing the length and decreasing the value hence still optimal

This is today's leetcode daily. Here is the link to my submission.

Now to prove this, notice that we need "any" number <= k, so, doesn't matter if its zero, it is still correct. Now, we can always have leading zeros is pretty easy to see. Starting from LSB, if we have one, we can "always" take it unless the number becomes > k. Why? B/c we are starting from LSB, so contribution would be least starting from this point. And since we only care about length, taking zero or one has same effect, only that one contributes to actual sum, zero doesn't.

From this, we can take a variable power to check the effect of adding this bit. Core idea of problem is to realize that the only preference to add is 1 from LSB side. Zeros are always welcome.

You can also see my Take / not take dp TLE sol here.

Hint: Think about how the binary value changes depending on the position of 1s.

Solution: Suppose we have two binary strings of length n:
s1 = 1000...000 and s2 = 0111...111.
Then, val(s1) = 2^n and val(s2) = 2^n — 1. So, s1 > s2.
Hence, it's always better to take 1s starting from the right (LSB) and include all the 0's as they virtually contribute nothing to the sum.

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        string s; cin >> s;
        int k; cin >> k;

        int ans = 0, n = s.size();

        for (int i = 0; i < n; i++) {
            if (s[i] == '0') ans++;
        }

        int val = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '1') {
                int bit = n - 1 - i;
                if (bit < 60 && val + (1LL << bit) <= k) {
                    val += (1LL << bit);
                    ans++;
                }
                else break;
            }
        }

        cout << ans << "\n";
    }
    return 0;
}