Long Beautiful Integer

Created by LXC on Wed May 17 09:11:45 2023

https://codeforces.com/problemset/problem/1268/A

ranting: 1700

tag: constructive algorithms, greedy, implementation, strings

题意

给出一个很大的整数a，a用数组表示，无前导0。再给出k。

求一个最小的b使得b>=a

b是一个漂亮整数，满足$b_i = b_{i-k}$

题解

b显然每k个位会循环一次。

所以确定了前k位就确定了后面的位数。

我们先让b的前k位变为a的前k位。比较b是否能大于等于a。

如果不能，则将前k位看作为一个数，让其加1。

代码

#include <bits/stdc++.h>
// #define LOCAL
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    auto t = s;
    for (int i = 0; i < n; i++) {
        t[i] = s[i % k];
    }
    if (t >= s) {
        cout << n << "\n" << t;
        return;
    } else {
        for (int i = k - 1; i >= 0; i--) {
            if (t[i] == '9') {
                for (int j = i; j < n; j += k)
                    t[j] = '0';
            } else {
                for (int j = i; j < n; j += k)
                    t[j] = s[i] + 1;
                cout << n << "\n" << t;
                return;
            }
        }
    }
}

int main() {
#ifdef LOCAL
    auto start_time = clock();
    cerr << setprecision(3) << fixed;
#endif
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
#ifdef LOCAL
    auto end_time = clock();
    cerr << "Execution time: "
         << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
    return 0;
}