Розбий#12368

Розбий (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготував:	Андрій Холод (Connect)
Розбір:	Андрій Холод (Connect)

Ідея

Нехай число задано рядком $s$ .

Оскільки довжина числа може сягати $2 \cdot 1 0^{5}$ 2 \cdot 10^5, працювати через стандартні цілі типи не вийде. Тому вся арифметика в рішенні робиться над рядками.

Ключове спостереження

Насправді достатньо перевірити лише два розрізи:

після першої цифри;
перед останньою цифрою.

Тобто кандидати такі:

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

Іншими словами:

або ліва частина складається лише з першої цифри;
або права частина складається лише з останньої цифри.

Чому цього достатньо? Якщо ми ріжемо десь всередині, то обидві частини втрачають частину "ваги" старших розрядів. У десятковому записі старші цифри значно важливіші за молодші, тому оптимум досягається тоді, коли одна з частин має довжину 1, а друга містить майже все число.

Отже задача зводиться до порівняння всього двох варіантів. Cуму та порівняння двох великих чисел можна реалізувати за допомогою довгої арифметики, що і є рішенням.

Асимптотика

Кожен із двох кандидатів будується за $O (n)$ , де $n$ — довжина рядка. Порівняння також працює за $O (n)$ .

Отже маємо $O (n)$ .

#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<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define ln log
#define lg log10
#define log log2
#define here cout<<"HERE"<<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++