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：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
char ch;
bool ok;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
const int maxn=;
int k,n;
const int MAXN=;
const int maxnum=;
struct bignum{
int len,v[MAXN];
bignum(){memset(v,,sizeof(v)),len=;}
bignum operator=(const char* num){
memset(v,,sizeof(v));
len=((strlen(num)-)>>)+;
int j=,k=;
for (int i=strlen(num)-;i>=;i--){
if (j==maxnum) j=,k++;
v[k]+=(num[i]-'')*j;
j*=;
}
return *this;
}
bignum operator=(const int num){
char a[MAXN<<];
sprintf(a,"%d",num);
*this=a;
return *this;
}
bignum (int num){*this=num;}
bignum (const char* num){*this=num;}
bignum operator+(const bignum &a){
bignum c;
c.len=max(len,a.len);
for (int i=;i<c.len;i++){
c.v[i]+=v[i]+a.v[i];
if (c.v[i]>=maxnum) c.v[i+]+=(c.v[i]/maxnum),c.v[i]%=maxnum;
}
while (c.v[c.len]) c.len++;
return c;
}
bignum operator-(const bignum b){
bignum a,c;
a=*this;
c.len=len;
for (int i=;i<len;i++){
if (a.v[i]<b.v[i]) a.v[i+]--,a.v[i]+=maxnum;
c.v[i]=a.v[i]-b.v[i];
}
while (c.len>&&!(c.v[c.len-])) c.len--;
return c;
}
bignum operator*(const bignum &a){
bignum c;
c.len=len+a.len;
for (int i=;i<len;i++)
for (int j=;j<a.len;j++){
c.v[i+j]+=v[i]*a.v[j];
if (c.v[i+j]>=maxnum) c.v[i+j+]+=(c.v[i+j]/maxnum),c.v[i+j]%=maxnum;
}
while (c.len>&&!(c.v[c.len-])) c.len--;
return c;
}
bignum operator*(const int &a){
bignum c=a;
return *this*c;
}
bignum operator/(const int &b){
bignum c;
int x=;
for (int i=len-;i>=;i--){
c.v[i]=(x*maxnum+v[i])/b;
x=(x*maxnum+v[i])%b;
}
c.len=len;
while (c.len>&&!(c.v[c.len-])) c.len--;
return c;
}
bignum operator+=(const bignum &a){*this=*this+a;return *this;}
bignum operator-=(const bignum &a){*this=*this-a;return *this;}
bignum operator*=(const bignum &a){*this=*this*a;return *this;}
bignum operator/=(const int &a){*this=*this/a;return *this;}
bool operator < (const bignum &x)const{
if (len!=x.len) return len<x.len;
for (int i=len-;i>=;i--)
if (v[i]!=x.v[i]) return v[i]<x.v[i];
return false;
}
bool operator > (const bignum &x)const{return x<*this;}
bool operator <=(const bignum &x)const{return !(x<*this);}
bool operator >=(const bignum &x)const{return !(*this<x);}
bool operator ==(const bignum &x)const{return !(x<*this||*this<x);}
bool operator !=(const bignum &x)const{return x<*this||*this<x;}
};
void write(bignum x){
printf("%d",x.v[x.len-]);
for (int i=x.len-;i>=;i--) printf("%0*d",,x.v[i]);
puts("");
}
void read(bignum &x){
static char num[MAXN<<];
scanf("%s",num);
x=num;
}
bignum l,r,m,pw2[maxn],sum[maxn],tmp,res,t,xx;
int a[maxn];
void init(){
pw2[]=;
for (int i=;i<=;i++) pw2[i]=pw2[i-]*;
sum[]=;
for (int i=;i<=;i++) sum[i]=sum[i-]*+pw2[i-];
}
void calc(){
tmp=,res=;
for (int i=;i<=k;i++) if (a[i]) res+=tmp+sum[i-],tmp+=pw2[i-];
}
void find(bignum lim){
bool flag=(lim>=sum[k]);
int tmp=;
for (int i=k;i>=;i--){
xx=sum[i-]+pw2[i-]*tmp;
if (lim>=xx) lim=lim-xx,tmp++,a[i]=;
else a[i]=;
}
if (!flag){
for (int i=;i<=k;i++){
a[i]^=;
if (!a[i]) break;
}
}
}
bool check(){
for (int i=;i<=k;i++) if (!a[i]) return false;
return true;
}
bool check(bignum lim){
bignum t=;
int cnt=n;
memset(a,,sizeof(a));
while (cnt--){
find(t+lim),calc(),t=res;
if (check()) return true;
}
return false;
}
int main(){
init();
read(k),read(n);
l=,r=sum[k];
while (l!=r){
m=(l+r)/;
if (check(m)) r=m; else l=m+;
}
write(l);
return ;
}