Problem A: Check multiples of 4

Given three digits a, b, c (most significant first), form the three-digit number n = 100*a + 10*b + c. Determine whether n is divisible by 4.

int a, b, c; cin >> a >> b >> c;
int n = a * 100 + b * 10 + c;
cout << (n % 4 == 0 ? "YES" : "NO") << "\n";

Problem B: Minimum travel distance

There are N points on a line at coordinates a[1..N]. Starting from an arbitrary point and ending at any point, find the shortest distance that visits all points.

Since the optimal path goes from the leftmost to the rightmost point without backtracking, the answer is max(a) - min(a).

int N; cin >> N;
vector<int> a(N);
for (int i = 0; i < N; ++i) cin >> a[i];
int mn = *min_element(a.begin(), a.end());
int mx = *max_element(a.begin(), a.end());
cout << mx - mn << "\n";

Variant: returning to start after each visit

If we must choose a starting point x, visit each given point, and return to x after each visit, the total distance becomes f(x) = sum_i |x - a_i|. This function is convex (unimodal).

Although ternary search on x might seem plausible, standard ternary search requires strict monotonicity on both sides of the minimum. Since f can have flat segments (when x lies between data points), ternary search is not safe.

We can instead compute f(x) for all possible integer x within the coordinate range [min_a, max_a]. For M = max_a - min_a + 1, we can compute f in O(M) using prefix sums:

• Let pre(c) = number of points with coordinate <= c.
• Then f(c) = f(c-1) + pre(c-1) - (N - pre(c)). (Derivation: moving from c-1 to c changes each distance by +1 for points left of c and -1 for points to the right.)

O(N) to compute pre, then O(M) to evaluate all f and find the minimum.

Problem C: Color counting from scores

Score inetrvals map to eight colors:

Given N scores x_i, each score >= 3200 can be assigned any of the eight colors. We need the minimum and maximum possible distinct colors.

• For each score, compute p = min(x / 400, 8) and increment cnt[p].
• Let fixed = number of p in [0..7] with cnt[p] > 0.
• Minimum colors = max(1, fixed) (if no fixed colors, we can still assign all scores to one color).
• Maximum colors = fixed + cnt[8] (all big scores get distinct colors if possible).

int N; cin >> N;
int cnt[9] = {0};
for (int i = 0; i < N; ++i) {
    int x; cin >> x;
    int p = min(x / 400, 8);
    cnt[p]++;
}
int fixed = 0;
for (int i = 0; i < 8; ++i) if (cnt[i]) ++fixed;
int mi = max(1, fixed);
int mx = fixed + cnt[8];
cout << mi << " " << mx << "\n";

Problem D: Complete parentheses to smallest lexicographic string

Given a string s of length n containing only ( and ), we may insert ( or ) anywhere to obtain a valid parentheses string. We want the shortest possible result, and among those, the lexicographically smallest (where ( < )).

Define a height array h[0..n]:h[0]=0, and for i=1..n, h[i] = h[i-1] + 1 if s[i]=='(' else h[i] = h[i-1] - 1. A valid string must satisfy h[i] >= 0 for all i and h[n] == 0.

Let d = -min_i h[i] (the deepest negative depth during traversal). We need to prepend d opening parentheses to keep height nonnegative. Then after the whole string, we need to append h[n] + d closing parentheses to bring final height back to zero.

For lexicographically smallest, we add all required ( at the beginning and all required ) at the end because ( comes before ) and placing them earlier yields a smaller string.

int n; string s;
cin >> n >> s;
int depth = 0, minDepth = 0;
for (char c : s) {
    depth += (c == '(' ? 1 : -1);
    minDepth = min(minDepth, depth);
}
int needOpen = -minDepth;
int needClose = depth + needOpen;
cout << string(needOpen, '(') << s << string(needClose, ')') << "\n";