题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include<bits/stdc++.h>

using namespace std;
#define inf 0x3f3f3f3f

typedef long long ll;
typedef pair<int,int> P;

#define pi 3.141592653589793238


int mov[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
int month[13]= {0,31,0,31,30,31,30,31,31,30,31,30,31};

const int N=10000;

class BigNum{
public:
    int num[20];
    BigNum(){
        memset(num,0,sizeof(num));
        num[0]=1;
    }
    BigNum operator=(const string& s){
        num[0]=0;
        int slen=s.length();
        for(int i=slen-4;i>=0;i-=4){
            int x=0;
            for(int j=0;j<4;j++){
                x=x*10+s[j+i]-'0';
            }
            num[++num[0]]=x;
        }
        if(slen%4!=0){
            int x=0;
            for(int i=0;i<slen%4;i++){
                x=x*10+s[i]-'0';
            }
            num[++num[0]]=x;
        }
        return *this;
    }
    BigNum operator=(const BigNum& Y){
        memset(num,0,sizeof(num));
        num[0]=Y.num[0];
        for(int i=0;i<=Y.num[0];i++){
            num[i]=Y.num[i];
        }
        return *this;
    }
    bool operator==(const BigNum& Y){
        if(num[0]!=Y.num[0]){
            return false;
        }
        for(int i=1;i<=num[0];i++){
            if(num[i]!=Y.num[i]){
                return false;
            }
        }
        return true;
    }
    bool operator>(const BigNum& Y){
        if(num[0]>Y.num[0]){
            return true;
        }
        if(num[0]<Y.num[0]){
            return false;
        }
        for(int i=num[0];i>=1;i--){
            if(num[i]>Y.num[i]){
                return true;
            }else if(num[i]<Y.num[i]){
                return false;
            }
        }
        return false;
    }
    BigNum operator+(const BigNum& Y){
        BigNum temp;
        int maxlen=max(num[0],Y.num[0]);
        temp.num[0]=maxlen;
        for(int i=1;i<=maxlen;i++){
            temp.num[i]+=num[i]+Y.num[i];
            temp.num[i+1]=temp.num[i]/N;
            temp.num[i]=temp.num[i]%N;
        }
        while(temp.num[maxlen]!=0){
            maxlen++;
        }
        temp.num[0]=maxlen-1;
        return temp;
    }
    BigNum operator-(const BigNum& Y){
        BigNum temp=*this;
        int minlen=min(num[0],Y.num[0]);
        for(int i=1;i<=minlen;i++){
            temp.num[i]-=Y.num[i];
            if(temp.num[i]<0){
                temp.num[i+1]-=1;
                temp.num[i]+=N;
            }
        }
        minlen++;
        while(temp.num[minlen]<0){
            temp.num[minlen]+=N;
            temp.num[minlen+1]-=1;
            minlen++;
        }
        while(temp.num[0]>1&&temp.num[num[0]]==0){
            temp.num[0]--;
        }
        return temp;
    }
    BigNum operator/(int div){
        BigNum res=*this;
        int x=0;
        for(int i=res.num[0];i>=1;i--){
            int t;
            t=(res.num[i]+x*N)/div;
            x=(res.num[i]+x*N)%div;
            res.num[i]=t;
        }
        while(res.num[0]>1&&res.num[res.num[0]]==0){
            res.num[0]--;
        }
        return res;
    }
};

int n;

int fun(BigNum big,BigNum des){
    BigNum x1=big;
    string st="1";
    BigNum sub;
    sub=st;
    for(int i=0;i<n;i++){
        x1=x1+x1-sub;
        big=big+x1;
        if(big>des){
            return 2;
        }
    }
    if(big==des){
        return 1;
    }
    return 3;
}

void print(BigNum x){
    for(int i=x.num[0];i>=1;i--){
        cout<<x.num[i];
    }
    cout<<endl;
}

int main()
{


    ios::sync_with_stdio(false);
    cin.tie(0);


    string s;
    cin>>n>>s;
    BigNum des;
    des=s;
    BigNum R;
    R=s;
    s="1";
    BigNum L;
    L=s;
    BigNum add;
    add=s;
    s="2";
    int div=2;

    while(R>L){
        BigNum mid=(R+L)/div;
        if(mid.num[0]==2&&mid.num[1]<5){
            int z;
            z=z+1;
        }
        int x=fun(mid,des);
        if(x==1){
            print(mid);
            break;
        }else if(x==2){
            R=mid;
        }else{
            L=mid+add;
        }
    }



    return 0;
}