Binary String (Problem L, 2018 ICPC Asia Jakarta Regional Contest, 2018)
Time limit: 0.5 sec
Memory limit: 256MB
Author: Jonathan Irvin Gunawan

# Problem Statement

A binary string is a non-empty sequence of 0’s and 1’s, e.g., 010110, 1, 11101, etc. Ayu has a favorite binary string $S$ which contains no leading zeroes. She wants to convert $S$ into its **decimal** representation with her calculator.

Unfortunately, her calculator cannot work on any integer larger than $K$ and it will crash. Therefore, Ayu may need to remove zero or more bits from $S$ while maintaining the order of the remaining bits such that its decimal representation is no larger than $K$. The resulting binary string also must not contain any leading zeroes.

Your task is to help Ayu to determine the minimum number of bits to be removed from $S$ to satisfy Ayu’s need.

For example, let $S = 1100101$ and $K = 13$. Note that $1100101$ is 101 in decimal representation, thus, we need to remove several bits from $S$ to make it no larger than $K$. We can remove the $3^{rd}$, $5^{th}$, and $6^{th}$ most significant bits, i.e. $1100101 \rightarrow 1101$. The decimal representation of $1101$ is 13, which is no larger than $K = 13$. In this example, we removed 3 bits, and this is the minimum possible (If we remove only 2 bits, then we will have a binary string of length 5 bits; notice that any binary string of length 5 bits has a value of at least 16 in decimal representation).

# Input

Input begins with a line containing an integer $K$ ($1 \le K \le 2^{60}$) representing the limit of Ayu’s calculator. The second line contains a binary string $S$ ($1 \le |S| \le 60$) representing Ayu’s favorite binary string. You may safely assume $S$ contains no leading zeroes.

# Output

Output contains an integer in a line representing the minimum number of bits to be removed from $S$.

# Sample Input #1
```
13
1100101
```
# Sample Output #1
```
3
```
# Explanation for the sample input/output #1

This sample is illustrated by the example given in the problem description above.

# Sample Input #2
```
13
1111111
```
# Sample Output #2
```
4
```
# Explanation for the sample input/output #2

Ayu must remove 4 bits to get 111, which is 7 in its decimal representation.


Sample inputs:
13
1100101

13
1111111

Sample outputs:
3

4

# Solution Analysis
Analysis author: Suhendry Effendy

At first glance, it looks like this problem can be solved by a greedy approach. Indeed, greedy works for this problem.

First, we should compute the length of the given $K$ in binary representation. Let’s say the length is $len(K)$. If $len(K) < |S|$, then simply output 0 as $K$ is already no larger than the decimal representation of $S$. The *real* problem is when $len(K) \ge |S|$.

If $len(K) > |S|$, we need to remove bits from $K$ such that its length in binary representation is at most $|S|$. The question is, which bit to remove? Our objective is to make $K$ as low as possible by removing a minimum number of bits. Thus, we should prioritize the **second** most significant 1 bit because it’s the second bit which contributes the most to the value of $K$. Note that the most significant 1 bit (the first one) cannot be removed as the problem states that the resulting binary string must not contain any leading zeroes. Perform this action repeatedly until $len(K) = |S|$ or there is no more 1 bit (except the most significant one). If there is no more 1 bit to be removed while $len(K) > |S|$, then remove any 0 bit to make $len(K) = |S|$. Once we get $len(K) = |S|$ with this method, we still need one additional check.

If $len(K) = |S|$ but $K$ is still larger than the decimal representation of $S$, then simply remove any one 0 bit from $K$, and we’re done.

Special judge (C++ scorer):