B Split a Number （字符求和）

Dima worked all day and wrote down on a long paper strip his favorite number $n$

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.

Input

The first line contains a single integer $l$

The second line contains the positive integer $n$

The integer $n$

Output

Print a single integer — the smallest number Dima can obtain.

Examples

Input

7
1234567

Output

Input

3
101

Output

Note

In the first example Dima can split the number $1234567$

In the second example Dima can split the number $101$

这个能过CF但是有BUG，但能 hack 死一大片（下面的样例），正确解法是记录非0位置，二分查计算

000034

会输出0034，很明显错误

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>

//
#define lson rt<<1, l, m
#define rson rt<<1|1, m+1, r


#define gcd __gcd
#define mem(s,t) memset(s,t,sizeof(s))
#define debug(a)   for(int i=1;i<=n;i++) cout<<" "<<a[i];  cout<<endl;
#define debug(a) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cout<<a[i][j]<<" ";   cout<<endl; }
#define read1(a)   for (int i = 1; i <= (int)n; i++)  {cin>>a[i]); }
#define read2(a) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cin>>a[i][j] ; }
#define TLE std::ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);   cout.precision(10);
#define fi      first
#define se      second
#define pb      push_back
#define pql     priority_queue<lli>
#define pq      priority_queue<int>
#define ok      return 0;
#define oi(x)   cout<<x<<endl;
#define os(str) cout<<string(str)<<endl;
using namespace std;
inline void NO()
{
    cout<<"NO
";
}
inline void YES()
{
    cout<<"YES
";
}
typedef long long lli;
typedef long double ld;
const int  N         = 1e5+5;
const int  logN      = (int)log2(N)+1;
const ld   PI        = acos(-1);
const ld   EPS       = 1e-10;
typedef pair < int, int > pii;
typedef pair < lli, lli > pll;
typedef vector < lli > vl;
typedef vector < int > vi;
multiset <int> ms;
#define rep(ttt,k)    for (int i=ttt;i<=k;i++)
#define per(ttt,k)    for (int i=ttt;i>=k;i--)
const int  mxn = 2e5+10;
int a[mxn];
/*
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
*/
string sum(string s1 , string s2)
{
    if(s1.size()<s2.size())
        swap(s1,s2);
    for(int i=0 ; i<s2.size();i++)
        s1[ s1.size()-s2.size()+i ] += s2[i]-'0';
    for( int i=s1.size()-1;i>=1;i--)
    {
        if(s1[i]>'9')
        {
            s1[i] -= 10;
            s1[i-1]++;
        }
    }
    if(s1[0]>'9')
    {
        s1[0]-=10;
        s1 = '1'+s1;
    }
    //cout<<s1<<endl;
    return s1;
}
string fun(string s1 , string s2)
{
    if(s1.size()<s2.size()) return s1;
    if(s1.size()>s2.size()) return s2;
    return s1<s2?s1:s2;
}
int main()
{
    int n;        string str,ch;
    cin>>n>>str;
    ch = str;
    int mid = n>>1;
    while(str[mid]=='0') mid--;
    if( str[mid]!='0' && mid>=0)
        ch = fun( ch , sum( str.substr(0,mid) , str.substr(mid) ) );
    mid = (n+1)>>1;
    while(mid<n && str[mid]=='0')
        mid++;
    if( str[mid]!='0' && mid<n )
        ch = fun( ch , sum( str.substr(0,mid) , str.substr(mid) ) );
    cout<<ch<<endl;
}

#include <bits/stdc++.h>
 
#define fi first
#define se second
 
const int N = 100100;
 
using namespace std;
 
int n;
char a[N];
 
string get(int x)
{
        vector < int > A, B;
        for(int i = x; i > 0; i--){
                A.push_back(a[i] - '0');
        }
        for(int i = n; i > x; i--){
                B.push_back(a[i] - '0');
        }
        while(A.size() < B.size()) A.push_back(0);
        while(B.size() < A.size()) B.push_back(0);
        A.push_back(0);
        for(int i = 0; i < B.size(); i++){
                A[i] += B[i];
                A[i + 1] += A[i] / 10;
                A[i] %= 10;
        }
        while(A.back() == 0) A.pop_back();
        string res = "";
        while(!A.empty()){
                res += char(A.back() + '0');
                A.pop_back();
        }
        return res;
}
 
int main()
{
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        ios_base::sync_with_stdio(0);
 
        cin >> n;
        string res = "";
        vector < int > v;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                res += "9";
                if(i < n){
                        v.push_back(i);
                }
        }
        sort(v.begin(), v.end(), [&](int x, int y){
                return abs(x - n / 2) > abs(y - n / 2);
             });
        for(int i = 0; i < 10; i++){
                while(!v.empty() && a[v.back() + 1] == '0'){
                        v.pop_back();
                }
                if(v.empty()){
                        break;
                }
                string can = get(v.back());
                v.pop_back();
                if(can.size() < res.size() || can.size() == res.size() && can < res){
                        res = can;
                }
        }
        cout << res << "
";
}

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 y00
 
//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll bt = 30;
const ld eps = 1e-9;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(2e9 + 239);
const int MOD = 1e9 + 7; //998244353;
const ll MOD2 = (ll)MOD * (ll)MOD;
 
//random
mt19937_64 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());
 
//constants
const int M = (int)(2e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 20;
const int T = (1 << 18);
const int B = (int)sqrt(M);
const int X = 1e4 + 239;
 
string sum(string s, string t)
{
    vector<int> ans(max((int)s.size(), (int)t.size()) + 1, 0);
    for (int i = (int)s.size() - 1; i >= 0; i--)
        ans[(int)s.size() - 1 - i] += s[i] - '0';
    for (int i = (int)t.size() - 1; i >= 0; i--)
        ans[(int)t.size() - 1 - i] += t[i] - '0';
    int p = 0;
    for (int i = 0; i < ans.size(); i++)
    {
        int ost = (p + ans[i]) % 10;
        p = (p + ans[i]) / 10;
        ans[i] = ost;
    }
    while (ans.back() == 0)
        ans.pop_back();
    string u = "";
    while (!ans.empty())
    {
        u += (char)('0' + ans.back());
        ans.pop_back();
    }
    return u;
}
 
int n;
string s;
 
string gett(int i)
{
    string s1 = "";
    for (int x = 0; x < i; x++)
        s1 += s[x];
    string s2 = "";
    for (int x = i; x < n; x++)
        s2 += s[x];
    return sum(s1, s2);
}
 
bool cmp(string a, string b)
{
    if ((int)a.size() != (int)b.size())
        return (int)a.size() < (int)b.size();
    return (a < b);
}
 
int32_t main()
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    vector<int> cand;
    int k = 0;
    for (int i = n / 2; i < n && k < 3; i++)
        if (s[i] != '0')
        {
            cand.push_back(i);
            k++;
        }
    k = 0;
    for (int i = n / 2; i >= 1 && k < 3; i--)
        if (s[i] != '0')
        {
            cand.push_back(i);
            k++;
        }
    vector<string> v;
    for (int i : cand)
        v.push_back(gett(i));
    sort(v.begin(), v.end(), cmp);
    cout << v[0];
    return 0;
}

所遇皆星河

B Split a Number （字符求和 ）

B Split a Number （字符求和）