Problem A – AB Balance

For each test case a string s (only the characters 'a' and 'b') is given. Let cntAB be the number of occurrences of the substring "ab" and cntBA the number of occurrences of "ba". The task is to make the two counts equal by changing at most one character of the string to 'a'. If the counts are already equal we output the original string; otherwise we replace either the first or the last character sothat the larger count is reduced by exactly one.

Algorithm

1. Scan the whole string once and count cntAB and cntBA.
2. If the counts are equal, print the string unchanged.
3. Otherwise
   • If cntBA > cntAB change the first character to 'a' (this removes exactly one "ba" that starts at position 0).
   • If cntAB > cntBA change the last character to 'a' (this removes exactly one "ab" that ends at position n‑2).
4. Output the resulting string.

Complexity Analysis

The scan takes O(|s|) time and only a constant amount of extra memory.

Reference Implementation (C++17)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    if(!(cin >> T)) return 0;
    while (T--) {
        string s;
        cin >> s;
        long long cntAB = 0, cntBA = 0;
        for (size_t i = 0; i + 1 < s.size(); ++i) {
            if (s[i] == 'a' && s[i+1] == 'b') ++cntAB;
            else if (s[i] == 'b' && s[i+1] == 'a') ++cntBA;
        }
        if (cntAB == cntBA) {
            cout << s << '\n';
        } else if (cntBA > cntAB) {
            s.front() = 'a';
            cout << s << '\n';
        } else {
            s.back() = 'a';
            cout << s << '\n';
        }
    }
    return 0;
}

Problem B – Update Files

You start with a single file and you may perform two kinds of operations:

• Double the current number of files (allowed only while the result is still smaller than a given limit k).
• Increase the number of files by at most k in a single step.

Given the target number n and the limit k, compute the minimum number of operations needed to reach or exceed n.

Algorithm

1. Initialize cur = 1 and ops = 0.
2. While cur < k and cur < n perform:
   • cur *= 2;
   • ++ops;
3. After the loop, if cur < n compute the remaining amount: ``` remaining = max(0LL, n - cur);

4. The number of additional "add‑k" operations required is ``` addOps = (remaining + k - 1) / k; // integer ceiling

5. Answer = ops + addOps.

Complexity Analysis

The doubling loop runs at most log₂(min(n, k)) times, so the total time is O(log min(n,k)) and the memory usage is O(1).

Reference Implementation (C++17)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        long long n, k;
        cin >> n >> k;
        long long cur = 1, ops = 0;
        while (cur < k && cur < n) {
            cur <<= 1;   // equivalent to cur *= 2
            ++ops;
        }
        long long remaining = max(0LL, n - cur);
        long long addOps = (remaining + k - 1) / k;   // ceiling division
        cout << ops + addOps << '\n';
    }
    return 0;
}

Problem C – Banknotes

There are n types of banknotes. The value of the i-th type is 10^{a_i}, where the exponents a_i are strictly increasing. You are allowed to use at most k notes in total (the exact number of each type is unlimited). The goal is to determine the smallest positive amount of money that cannot be formed under this restriction.

Key Observation

For two consecutive denominations 10^{a_i} and 10^{a_{i+1}} we have

10^{a_i} * (10^{a_{i+1} - a_i}) = 10^{a_{i+1}}.

Consequently, using more than 10^{a_{i+1} - a_i} - 1 notes of the smaller denomination would be interchangeable with a single note of the larger denomination. Let

limit_i = 10^{a_{i+1} - a_i} - 1   (for i < n-1)

limit_{n-1} = +∞   // effectively no bound for the largest note

limit_i is the maximal number of notes of value 10^{a_i} we can safely take without being forced to replace them by a note of the next higher value.

Greedy Construction

Starting from the smallest denomination and moving upward we try to consume as many notes as the current limit permits while we still have remaining "budget" k.

1. If k > limit_i we can take all limit_i notes: ``` ans += limit_i * 10^{a_i}; k -= limit_i;

2. Otherwise k ≤ limit_i. Taking k+1 notes of this denomination already exceeds the limit, so the smallest unattainable sum is (k+1) * 10^{a_i}. We output this value and stop processing further denominations.

If the loop finishes (which can happen only for the last denomination), the answer is (k+1) * 10^{a_{n-1}}.

Algorithm

read n, k
read array a[0..n-1]
ans = 0
for i = 0 .. n-1
    if i+1 < n
        diff = a[i+1] - a[i]
        limit = pow10(diff) - 1      // pow10 returns 10^diff as 64‑bit integer
    else
        limit = 1e18                 // "infinite" for the largest denomination

    if limit > k
        ans += (k + 1) * pow10(a[i])
        break
    else
        ans += limit * pow10(a[i])
        k   -= limit
output ans

Complexity Analysis

Each test case performs a single linear pass over the n exponents, so the time complexity is O(n). Only a few 64‑bit variables are stored, giving O(1) extra memory.

Reference Implementation (C++17)

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

// compute 10^exp safely for small exponents (exp ≤ 9 fits in 64‑bit)
long long pow10(int exp) {
    long long r = 1;
    while (exp--) r *= 10LL;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long k;
        cin >> n >> k;
        vector<int> a(n);
        for (int &x : a) cin >> x;

        long long answer = 0;
        for (int i = 0; i < n; ++i) {
            long long limit;
            if (i + 1 < n) {
                int diff = a[i + 1] - a[i];
                limit = pow10(diff) - 1;               // maximum notes before we would switch
            } else {
                limit = (long long)4e18;               // virtually unlimited
            }

            if (limit > k) {                         // cannot take all limit notes
                answer += (k + 1) * pow10(a[i]);
                break;
            } else {
                answer += limit * pow10(a[i]);
                k -= limit;
            }
        }
        cout << answer << '\n';
    }
    return 0;
}