问题 K: Binary String

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

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 3rd, 5th, and 6th most significant bits, i.e. 1100101->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 begins with a line containing an integer K (1≤K≤260) representing the limit of Ayu’s calculator.

The second line contains a binary string S (1≤|S|≤60) representing Ayu’s favorite binary string. You may safely assume S contains no leading zeroes.

输出

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

样例输入

13

1100101

样例输出

3

提示

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

队友过的，听说挺简单的

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N =105;
typedef pair<int,int>P;

ll k;
char s[N];
int lens,lenk,cnt0;

inline int getlen(ll x)
{
    int ans=0;
    while(x)
    {
        x>>=1;
        ans++;
    }
    return ans;
}

inline ll getsum()
{
    ll ret=0;
    for(int i=0;i<lens;i++)
    {
        if(s[i]=='1') ret+=(1ll<<(lens-1-i));
        else cnt0++;
    }
    return ret;
}
int main()
{
    //freopen("a.txt","r",stdin);
    scanf("%lld",&k);
    scanf("%s",s);
    lens=strlen(s);
    lenk=getlen(k);
    ll sn=getsum();
    //cout<<sn<<endl;
    //cout<<lenk<<' '<<lens<<endl;
    if(sn<=k)
    {
        puts("0");
        return 0;
    }
    ll temp=1ll<<(lenk-1);
    int cnt1=lenk-cnt0-1;
    int digit=0;
    for(int i=lens-1;i>0;i--)
    {
        if(cnt1<=0) break;
        if(s[i]=='1')
        {
            temp+=(1ll<<digit);
            cnt1--;
        }
        digit++;
    }
    //cout<<temp<<endl;
    if(temp<=k)  printf("%d\n",lens-lenk);
    else printf("%d\n",lens-lenk+1);
    return 0;
}