Codeforces Round #609 (Div. 1) A. Long Beautiful Integer (R1700)

こういうのは、いかにシンプルにできるか...

問題へのリンク

問題概要

桁の整数 が与えられる (文字列として)。leading zero はない。整数 が与えられる。 以上の整数 であって

• の 桁目と 桁目の値は等しい

という条件を満たす最小値を求めよ。

制約

• 

考えたこと

落ち着くんだ...ひとまず、最悪でも 999...9 (N 桁) が条件を満たすので、桁数を増やす必要はない。あと、上から 桁分を決めれば全部決まるので、上から 桁を決める問題ということになる。

• もし、上から 桁のところが元のままでも、それを繰り返したときに 以上になるなら、それが答え
• それが 未満であるならば、上から 桁の部分を 1 増やしたものが答え

ということになる。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
 
int N, K;
string a;
 
string plusone(string s) {
    int id = (int)s.size() - 1;
    while (s[id] == '9') {
        s[id] = '0';
        --id;
    }
    ++s[id];
    return s;
}
 
string solve() {
    string b = a;
    for (int i = K; i < N; ++i) b[i] = a[i%K];
    if (b >= a) return b;
    string res = "";
    string prefix = plusone(a.substr(0, K));
    for (int i = 0; i < N; ++i) res += prefix[i%K];
    return res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    while (cin >> N >> K >> a) {
        string res = solve();
        cout << res.size() << endl;
        cout << res << endl;
    }
}