Böl#12368

Böl (Həll təhlili)

Müəllif:	Andrey Xolod (Connect)
Hazırlayan:	Andrey Xolod (Connect)
Təhlil:	Andrey Xolod (Connect)

Fikir

Təsəvvür edin ki, ədəd $s$ sətiri ilə verilib.

Ədədin uzunluğu $2 \cdot 1 0^{5}$ 2 \cdot 10^5-ə çata biləcəyinə görə, standart tam tipli ədədlərlə işləmək mümkün olmayacaq. Buna görə də, həllin bütün arifmetikası sətirlər üzərində aparılır.

Açar müşahidə

Əslində yalnız iki kəsik yoxlamaq kifayətdir:

birinci rəqəmdən sonra;
sonuncu rəqəmdən əvvəl.

Yəni namizədlər belədir:

$s_{0} + value (s [1.. n - 1])$ s_0 + \text{value}(s[1..n-1]) və $value (s [0.. n - 2]) + s_{n - 1}$ \text{value}(s[0..n-2]) + s_{n-1}

Başqa sözlə:

ya sol tərəf yalnız birinci rəqəmdən ibarətdir;
ya da sağ tərəf yalnız sonuncu rəqəmdən ibarətdir.

Niyə bu kifayətdir? Əgər biz içəridən bir yerdə kəsiriksə, o zaman hər iki hissə daha yüksək sıraların "ağırlığının" bir hissəsini itirir. Onluq sistemdə daha yüksək rəqəmlər daha aşağı rəqəmlərdən əhəmiyyətlidir, buna görə də optimal vəziyyət, bir hissənin uzunluğunun 1 olduğu, digərinin isə demək olar ki, bütün ədədi ehtiva etdiyi zaman əldə edilir.

Beləliklə, problem yalnız iki variantı müqayisə etməyə gətirilir. İki böyük ədədin cəmini və müqayisəsini uzun arifmetika vasitəsilə həyata keçirmək mümkündür, bu da həllin özüdür.

Asimptotika

Hər iki namizəd $O (n)$ vaxtında qurulur, burada $n$ - sətirin uzunluğudur. Müqayisə də $O (n)$ vaxtında işləyir.

Beləliklə, $O (n)$ əldə edirik.

#include <bits/stdc++.h>
#include <random>
// fast_pragmas

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")

// fast_pragmas ended

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

#define ull unsigned long long
#define ll long long
#define ld long double
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define yes cout<<"BƏLİ"<<endl
#define no cout<<"XƏTA"<<endl
#define pb push_back
#define ln log
#define lg log10
#define log log2
#define here cout<<"BURADADIR"<<endl

const ll clasik = 5e5 + 7;
const ll mln = 1e6 + 7;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const ll block_size = 450;
const ll INF = 1e17;

ll df[clasik];

string normalize(string s) {
    int i = 0;
    while (i + 1 < (int)s.size() && s[i] == '0') i++;
    return s.substr(i);
}

string addDigit(string num, int d) {
    int carry = d;
    for (int i = (int)num.size() - 1; i >= 0 && carry > 0; i--) {
        int cur = (num[i] - '0') + carry;
        num[i] = char('0' + (cur % 10));
        carry = cur / 10;
    }
    if (carry > 0) num.insert(num.begin(), char('0' + carry));
    return normalize(num);
}

bool greaterNumber(string a, string b) {
    if ((int)a.size() != (int)b.size()) return (int)a.size() > (int)b.size();
    return a > b;
}

void solve() {
    string s;
    cin >> s;

    int n = (int)s.size();

    if (n == 2) {
        int ans = (s[0] - '0') + (s[1] - '0');
        cout << ans << endl;
        return;
    }

    string option1 = addDigit(s.substr(1), s[0] - '0');
    string option2 = addDigit(s.substr(0, n - 1), s[n - 1] - '0');

    if (greaterNumber(option1, option2)) cout << option1 << endl;
    else cout << option2 << endl;
}

signed main() {

    //freopen("deciding_points_input.txt" , "r" , stdin);
    //freopen("outputA.txt" , "w" , stdout);

    speed;
    int test;
    test = 1;
    //precalc();
    //cin >> test;
    for (int tt = 1; tt <= test; tt++) {
        //cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

C++