A

Problem: You need to stay for (n) consecutive days. The pricing is (x) yuan per night for the first (k) days, and (y) yuan per night thereafter. What is the total cost?

Solution: (min(k, n) \cdot x + max(n - k, 0) \cdot y)

B

Problem: Given a string (s), determine if it is "beautiful". A string is beautiful if every lowercase character appears an even number of times. Otherwise, it is not.

(1 \leq |s| \leq 100)

Solution: Track the parity of each lowercase letter's occurrence count.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string str;
    cin >> str;
    
    vector<int> cnt(26, 0);
    for (char ch : str) {
        if ('a' <= ch && ch <= 'z') {
            cnt[ch - 'a'] ^= 1;
        }
    }
    
    bool beautiful = true;
    for (int i = 0; i < 26; i++) {
        beautiful &= (cnt[i] == 0);
    }
    
    cout << (beautiful ? "Yes" : "No") << "\n";
    return 0;
}

C

Problem: Given (n) numbers (a_1, a_2, \ldots, a_n) and a value (m), count the number of ways to select at least one number such that their average equals (m). Different selection orders are considered the same way.

(1 \leq n, m, a_i \leq 50)

Solution: This is a classic subset selection problem with constraints on both count and sum. Use dynamic programming where (dp[j][k]) represents the number of ways to select exactly (j) numbers with total sum (k).

The transition:

• Skip (a_i): (dp[j][k] += dp[j][k])
• Include (a_i): (dp[j][k] += dp[j-1][k-a_i])

Since we need (avg = m), we require (sum = j \cdot m) for (j) selected numbers.

Time complexity: (O(n \cdot m \cdot V)) where (V = \sum a_i \leq 2500). Maximum value fits in 64-bit integers.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, targetAvg;
    cin >> n >> targetAvg;
    vector<int> values(n + 1);
    int totalSum = 0;
    
    for (int i = 1; i <= n; i++) {
        cin >> values[i];
        totalSum += values[i];
    }
    
    vector<vector<int64>> dp(n + 1, vector<int64>(totalSum + 1, 0));
    dp[0][0] = 1;
    
    for (int idx = 1; idx <= n; idx++) {
        for (int cnt = idx; cnt >= 1; cnt--) {
            for (int sum = 0; sum <= totalSum; sum++) {
                if (sum >= values[idx]) {
                    dp[cnt][sum] += dp[cnt - 1][sum - values[idx]];
                }
            }
        }
    }
    
    int64 answer = 0;
    for (int cnt = 1; cnt <= n; cnt++) {
        for (int sum = 1; sum <= totalSum; sum++) {
            if (sum == cnt * targetAvg) {
                answer += dp[cnt][sum];
            }
        }
    }
    
    cout << answer << "\n";
    return 0;
}

D

Problem: For any positive integers (b (b \geq 2)) and (n (n \geq 1)), define (f(b, n)) as:

[f(b, n) = \begin{cases} n & \text{if } n < b \ f(b, \lfloor \frrac{n}{b} \rfloor) + n \bmod b & \text{if } n \geq b \end{cases}]
Given positive itnegers (n) and (s), determine if there exists a base (b (b \geq 2)) such that (f(b, n) = s). If it exists, find the minimum (b).

(1 \leq n, s \leq 10^{11})

Solution: The function (f(b, n)) computes the sum of digits when (n) is represented in base (b).

Key observations:

• If (n < s): impossible (digit sum cannot be less than the number of digits)
• If (n = s): answer is (s + 1) (representation is single digit in any base > s)
• If (n > s): base (b) must be in range ([2, n])

Sqrt decomposition approach:

1. Small bases (b \in [2, \sqrt{n})): Enumerate directly, computing digit sum in (O(\log_b n)) each.

2. Large bases (b \geq \sqrt{n}): When (b > \sqrt{n}), (n) has at most 2 digits in base (b). Represent (n = a_0 + a_1 \cdot b) where (0 \leq a_0, a_1 < b).

   From (f(b, n) = a_0 + a_1 = s) and (n = a_0 + a_1 \cdot b), we derive: (a_1 \cdot (b - 1) = n - s)

   Since (b \geq \sqrt{n} + 1), we can enumerate possible values of (a_1) within a bounded range and compute (b = \frac{n - s}{a_1} + 1).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int64 n, targetSum;
    cin >> n >> targetSum;
    const int64 UNREACHABLE = -1;
    int64 result = LLONG_MAX;
    
    if (n < targetSum) {
        cout << UNREACHABLE << "\n";
        return 0;
    }
    
    if (n == targetSum) {
        cout << (targetSum + 1) << "\n";
        return 0;
    }
    
    int64 limit = static_cast<int64>(sqrt(n)) + 2;
    
    // Case 1: enumerate small bases
    for (int64 base = 2; base < limit; base++) {
        int64 val = n, digitSum = 0;
        while (val > 0) {
            digitSum += val % base;
            val /= base;
        }
        if (digitSum == targetSum) {
            result = min(result, base);
        }
    }
    
    // Case 2: handle large bases (at most 2 digits)
    // Derive a1 from: a1 * (b - 1) = n - s, with constraints
    int64 lower = max<int64>(1, (n - targetSum + n - 2) / (n - 1));
    int64 upper = min(limit - 1, (n - targetSum) / (limit - 1));
    
    for (int64 a1 = lower; a1 <= upper; a1++) {
        if ((n - targetSum) % a1 != 0) continue;
        
        int64 base = (n - targetSum) / a1 + 1;
        int64 a0 = targetSum - a1;
        
        // Validate all constraints
        if (base >= limit && base <= n && 
            a0 >= 0 && a0 < base && a1 >= 1 && a1 < base && 
            a0 + a1 == targetSum) {
            result = min(result, base);
        }
    }
    
    if (result == LLONG_MAX) result = UNREACHABLE;
    cout << result << "\n";
    return 0;
}

Complexity analysis:

• Small base enumeration: (O(\sqrt{n} \cdot \log_n)) ≈ (O(\sqrt{n}))
• Large base solving: (O(\sqrt{n})) by bounding the enumeration range
• Overall: (O(\sqrt{n})) time, (O(1)) extra space