Problem A: Counting Digit Holes

The task requires calculating the total number of closed loops (holes) in a sequence of digits. Digits '0', '6', and '9' contain one loop each, while '8' contains two loops. The solution involves iterating through the string and accumulating the count based on the digit encountered.

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string input_num;
    cin >> input_num;

    int total_loops = 0;
    for (char digit : input_num) {
        switch (digit) {
            case '0':
            case '6':
            case '9':
                total_loops += 1;
                break;
            case '8':
                total_loops += 2;
                break;
        }
    }

    cout << total_loops << '\n';
    return 0;
}

Problem B: Vertical Multiplication Simulation

This problem simulates the process of vertical multiplication by taking two integers, $a$ and $b$, and summing the product of $a$ with each digit of $b$. We decompose $b$ digit by digit using modulo operations and accumulate the result.

#include <iostream>

using namespace std;

typedef long long ll;

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

    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        ll a, b;
        cin >> a >> b;
        ll sum = 0;

        while (b > 0) {
            int current_digit = b % 10;
            sum += current_digit * a;
            b /= 10;
        }

        cout << sum << '\n';
    }
    return 0;
}

Problem C: Minimizing Numerical Distance

We need to minimize the expression $|x! \cdot y - y - n|$, which simplifies to $|y(x! - 1) - n|$. To solve this, we iterate through possible values of $x$ (up to 10). For each $x$, we calculate the corresponding $y$ as $n / (x! - 1)$. The optimal solution is likely found at either the floor or the ceiling of this division. Note that $y$ must be positive and not equal to 2 based on specific problem constraints.

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

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

    ll n;
    cin >> n;

    ll best_x = 1, best_y = 1;
    ll factorial = 2;
    ll min_diff = n;

    for (ll x = 3; x <= 10; ++x) {
        factorial *= x;
        ll denominator = factorial - 1;
        
        ll candidate_y = n / denominator;
        
        // Check floor value
        if (candidate_y > 0 && candidate_y != 2) {
            ll diff = abs(candidate_y * denominator - n);
            if (diff <= min_diff) {
                min_diff = diff;
                best_x = x;
                best_y = candidate_y;
            }
        }

        // Check ceil value (floor + 1)
        candidate_y++;
        if (candidate_y > 0 && candidate_y != 2) {
            ll diff = abs(candidate_y * denominator - n);
            if (diff <= min_diff) {
                min_diff = diff;
                best_x = x;
                best_y = candidate_y;
            }
        }
    }

    cout << best_x << ' ' << best_y << '\n';
    return 0;
}

Problem D: Constructing a k-Good Array

To ensure every subarray of length $k$ has the same sum, elements at positions $i$, $i+k$, $i+2k$, etc., must be equal. We first determine the maximum value for each group of indices modulo $k$. Then we calculate the total increments needed to raise all elements in the group to this maximum. If the required increments exceed the budget $x$, the task is impossible. Otherwise, we distribute the remaining budget evenly among the groups to maximize the final peak value.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

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

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        ll budget;
        cin >> n >> k >> budget;
        
        vector<ll> sequence(n);
        vector<ll> max_in_group(k, 0);

        for (int i = 0; i < n; ++i) {
            cin >> sequence[i];
            int group_id = i % k;
            max_in_group[group_id] = max(max_in_group[group_id], sequence[i]);
        }

        ll required = 0;
        for (int i = 0; i < n; ++i) {
            required += max_in_group[i % k] - sequence[i];
        }

        if (required > budget) {
            cout << -1 << '\n';
            continue;
        }

        ll remaining = budget - required;
        ll result = 0;

        for (int i = 0; i < k; ++i) {
            // Number of elements in this group
            int count = n / k + (n % k > i);
            ll potential_max = max_in_group[i] + remaining / count;
            result = max(result, potential_max);
        }

        cout << result << '\n';
    }
    return 0;
}

Problem E: Length of Recurring Decimal Period

Given a fraction $p/q$, we need to find the length of the non-repeating part and the repeating part of its decimal expansion. First, we reduce the fraction by dividing $p$ and $q$ by their GCD. The length of the non-repeating part is determined by the maximum exponent of 2 or 5 in the prime factorization of $q$. After removing these factors, if the remaining $q$ is 1, the decimal terminates. Otherwise, the length of the repeating part is the smallest integer $d$ such that $10^d \equiv 1 \pmod q$. We can find $d$ by checking the divisors of Euler's totient functon $\phi(q)$.

#include <iostream>
#include <numeric>

using namespace std;

typedef long long i64;
typedef __int128 i128;

i128 fast_pow(i128 base, i64 exp, i64 mod) {
    i128 res = 1;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

i64 compute_euler_totient(i64 n) {
    i64 result = n;
    for (i64 i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            result -= result / i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

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

    i64 numerator, denominator;
    cin >> numerator >> denominator;

    i64 common_divisor = gcd(numerator, denominator);
    denominator /= common_divisor;

    i64 count_2 = 0, count_5 = 0;
    while (denominator % 2 == 0) { denominator /= 2; ++count_2; }
    while (denominator % 5 == 0) { denominator /= 5; ++count_5; }

    if (denominator == 1) {
        cout << "-1\n";
        return 0;
    }

    i64 totient = compute_euler_totient(denominator);
    i64 min_period = 1e16;

    for (i64 i = 1; i * i <= totient; ++i) {
        if (totient % i == 0) {
            if (fast_pow(10, i, denominator) == 1) min_period = min(min_period, i);
            if (fast_pow(10, totient / i, denominator) == 1) min_period = min(min_period, totient / i);
        }
    }

    cout << max(count_2, count_5) << " " << min_period << '\n';
    return 0;
}