You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partition the sequence into M chunks. Each chunk must be a consecutive subsequence of the original sequence. Let Si (1 ≤ i ≤ M) be the total number of 1's in all numbers in the ith chunk when written in binary, and let S be the maximum of all Si, i.e. the maximum number of 1's in any chunk. Your goal is to minimize S.
Input
In the first line of input, two numbers, K and M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100, M ≤ 2^K), are given, separated by a single space character.
Output
In one line of the output, write the minimum S that can be obtained by some split. Write it without leading zeros. The result is not guaranteed to fit in a 64-bit integer.
Example
Input:
3 4
Output:
4
题解：
from 算法合集之《浅谈数位类统计问题》
code：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 char ch; 8 bool ok; 9 void read(int &x){ 10 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1; 11 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); 12 if (ok) x=-x; 13 } 14 const int maxn=105; 15 int k,n; 16 const int MAXN=10; 17 const int maxnum=10000; 18 struct bignum{ 19 int len,v[MAXN]; 20 bignum(){memset(v,0,sizeof(v)),len=1;} 21 bignum operator=(const char* num){ 22 memset(v,0,sizeof(v)); 23 len=((strlen(num)-1)>>2)+1; 24 int j=1,k=0; 25 for (int i=strlen(num)-1;i>=0;i--){ 26 if (j==maxnum) j=1,k++; 27 v[k]+=(num[i]-'0')*j; 28 j*=10; 29 } 30 return *this; 31 } 32 bignum operator=(const int num){ 33 char a[MAXN<<2]; 34 sprintf(a,"%d",num); 35 *this=a; 36 return *this; 37 } 38 bignum (int num){*this=num;} 39 bignum (const char* num){*this=num;} 40 bignum operator+(const bignum &a){ 41 bignum c; 42 c.len=max(len,a.len); 43 for (int i=0;i<c.len;i++){ 44 c.v[i]+=v[i]+a.v[i]; 45 if (c.v[i]>=maxnum) c.v[i+1]+=(c.v[i]/maxnum),c.v[i]%=maxnum; 46 } 47 while (c.v[c.len]) c.len++; 48 return c; 49 } 50 bignum operator-(const bignum b){ 51 bignum a,c; 52 a=*this; 53 c.len=len; 54 for (int i=0;i<len;i++){ 55 if (a.v[i]<b.v[i]) a.v[i+1]--,a.v[i]+=maxnum; 56 c.v[i]=a.v[i]-b.v[i]; 57 } 58 while (c.len>1&&!(c.v[c.len-1])) c.len--; 59 return c; 60 } 61 bignum operator*(const bignum &a){ 62 bignum c; 63 c.len=len+a.len; 64 for (int i=0;i<len;i++) 65 for (int j=0;j<a.len;j++){ 66 c.v[i+j]+=v[i]*a.v[j]; 67 if (c.v[i+j]>=maxnum) c.v[i+j+1]+=(c.v[i+j]/maxnum),c.v[i+j]%=maxnum; 68 } 69 while (c.len>1&&!(c.v[c.len-1])) c.len--; 70 return c; 71 } 72 bignum operator*(const int &a){ 73 bignum c=a; 74 return *this*c; 75 } 76 bignum operator/(const int &b){ 77 bignum c; 78 int x=0; 79 for (int i=len-1;i>=0;i--){ 80 c.v[i]=(x*maxnum+v[i])/b; 81 x=(x*maxnum+v[i])%b; 82 } 83 c.len=len; 84 while (c.len>1&&!(c.v[c.len-1])) c.len--; 85 return c; 86 } 87 bignum operator+=(const bignum &a){*this=*this+a;return *this;} 88 bignum operator-=(const bignum &a){*this=*this-a;return *this;} 89 bignum operator*=(const bignum &a){*this=*this*a;return *this;} 90 bignum operator/=(const int &a){*this=*this/a;return *this;} 91 bool operator < (const bignum &x)const{ 92 if (len!=x.len) return len<x.len; 93 for (int i=len-1;i>=0;i--) 94 if (v[i]!=x.v[i]) return v[i]<x.v[i]; 95 return false; 96 } 97 bool operator > (const bignum &x)const{return x<*this;} 98 bool operator <=(const bignum &x)const{return !(x<*this);} 99 bool operator >=(const bignum &x)const{return !(*this<x);} 100 bool operator ==(const bignum &x)const{return !(x<*this||*this<x);} 101 bool operator !=(const bignum &x)const{return x<*this||*this<x;} 102 }; 103 void write(bignum x){ 104 printf("%d",x.v[x.len-1]); 105 for (int i=x.len-2;i>=0;i--) printf("%0*d",4,x.v[i]); 106 puts(""); 107 } 108 void read(bignum &x){ 109 static char num[MAXN<<2]; 110 scanf("%s",num); 111 x=num; 112 } 113 bignum l,r,m,pw2[maxn],sum[maxn],tmp,res,t,xx; 114 int a[maxn]; 115 void init(){ 116 pw2[0]=1; 117 for (int i=1;i<=101;i++) pw2[i]=pw2[i-1]*2; 118 sum[0]=0; 119 for (int i=1;i<=101;i++) sum[i]=sum[i-1]*2+pw2[i-1]; 120 } 121 void calc(){ 122 tmp=1,res=0; 123 for (int i=1;i<=k;i++) if (a[i]) res+=tmp+sum[i-1],tmp+=pw2[i-1]; 124 } 125 void find(bignum lim){ 126 bool flag=(lim>=sum[k]); 127 int tmp=0; 128 for (int i=k;i>=1;i--){ 129 xx=sum[i-1]+pw2[i-1]*tmp; 130 if (lim>=xx) lim=lim-xx,tmp++,a[i]=1; 131 else a[i]=0; 132 } 133 if (!flag){ 134 for (int i=1;i<=k;i++){ 135 a[i]^=1; 136 if (!a[i]) break; 137 } 138 } 139 } 140 bool check(){ 141 for (int i=1;i<=k;i++) if (!a[i]) return false; 142 return true; 143 } 144 bool check(bignum lim){ 145 bignum t=0; 146 int cnt=n; 147 memset(a,0,sizeof(a)); 148 while (cnt--){ 149 find(t+lim),calc(),t=res; 150 if (check()) return true; 151 } 152 return false; 153 } 154 int main(){ 155 init(); 156 read(k),read(n); 157 l=1,r=sum[k]; 158 while (l!=r){ 159 m=(l+r)/2; 160 if (check(m)) r=m; else l=m+1; 161 } 162 write(l); 163 return 0; 164 }