题目描述

给一个比较长的正整数 $n$，你可以在 $n$ 某些数字之间添加一些加号 +。例如 $n=123456$，可以添加加号得到 $12+34+56=102$。

再给出目标正整数 $m$，你需要让 $n$ 添加加号以后得到的式子尽量接近 $m$。问最接近 $m$ 的数是多少。

输入格式

从标准输入读入数据。

输入第一行包含一个正整数 $n$，第二行包含一个正整数 $m$。

输出格式

输出到标准输出。

输出 $n$ 添加加号以后能得到的最接近 $m$ 的数。如果有两个和 $m$ 一样接近的数都能得到，输出较大的那一个。

样例1输入

51938379
321

样例1输出

306

样例1解释

以这种方式添加号：$51+93+83+79=306$，可以证明没有更接近 $321$ 的方案。

样例2输入

242466971706670432
1

样例2输出

76

样例3输入

93200457137823030524
21376123

样例3输出

20869367

子任务

对于测试点 1，满足 $n \le 10^{ 8 }, m \le 1$。

对于测试点 2，满足 $n \le 10^{ 8 }, m \le 100000000$。

对于测试点 3，满足 $n \le 10^{ 18 }, m \le 1$。

对于测试点 4，满足 $n \le 10^{ 18 }, m \le 100000000$。

对于测试点 5，满足 $n \le 10^{ 24 }, m \le 1$。

对于测试点 6，满足 $n \le 10^{ 24 }, m \le 100000000$。

对于测试点 7，满足 $n \le 10^{ 27 }, m \le 100000000$。

对于测试点 8，满足 $n \le 10^{ 28 }, m \le 100000000$。

对于测试点 9，满足 $n \le 10^{ 30 }, m \le 100000000$。

对于测试点 10，满足 $n \le 10^{ 32 }, m \le 100000000$。

我的代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<ll> v1, v2;
vector<int> vec;
int mid;
string s, t;

void calc(vector<ll> &v) {
    vec.push_back(((v == v1 ? -1 : mid - 1)));
    vec.push_back((v == v2 ? (int)s.size() - 2 : mid - 1));
    sort(vec.begin(), vec.end());
    ll res = 0;
    for (int i = 1; i < (int)vec.size(); i++) {
        string s2 = s.substr(vec[i - 1] + 1, vec[i] - vec[i - 1]);
        if (s2.size() > 0) {
            res += stoll(s2);
        }
    }
    v.push_back(res);
}

void dfs1(int pos) {
    if (pos == mid) {
        calc(v1);
        return;
    }
    if (pos - (vec.empty() ? -1 : vec.back()) > 8) {
        goto nxt;
    }
    vec.push_back(pos);
    dfs1(pos + 1);
    vec.pop_back();
    dfs1(pos + 1);
nxt:;
}

void dfs2(int pos) {
    if (pos == (int)s.size() - 1) {
        calc(v2);
        return;
    }
    if (pos - (vec.empty() ? pos - mid + 1 : vec.back()) > 8) {
        goto nxt;
    }
    vec.push_back(pos);
    dfs2(pos + 1);
    vec.pop_back();
    dfs2(pos + 1);
nxt:;
}

int main() {
    cin >> s >> t;
    ll m = stoll(t);
    ll ans = -1e18;
    int l = (int)s.size() / 2 - 5;
    int r = (int)s.size() / 2 + 6;
    for (int i = max(0, l); i < min((int)s.size() - 1, r); i++) {  // 枚举中间加号的位置
        v1.clear();
        v2.clear();
        vec.clear();
        mid = i;
        dfs1(0);  // 截止到 mid
        vec.clear();
        dfs2(mid);
        for (auto x : v1) {
            int y = upper_bound(v2.begin(), v2.end(), m - x) - v2.begin();
            if (y < (int)v2.size()) {
                if (abs(ans - m) > abs(v2[y] - m)) {
                    ans = v2[y];
                } else if (abs(ans - m) == abs(v2[y] - m) && ans < v2[y]) {
                    ans = v2[y];
                }
            }
            y--;
            if (y >= 0) {
                if (abs(ans - m) > abs(v2[y] - m)) {
                    ans = v2[y];
                } else if (abs(ans - m) == abs(v2[y] - m) && ans < v2[y]) {
                    ans = v2[y];
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}