Problem A: Team Selection (5/5)

As a basketball coach, you need to pick one player for each position from 1 to 5 to form the starting lineup. The table below shows each player's rating for each position. Find the maximum total rating for the starting five.

Solution approaches:

1. Direct observation (mental deduction) – fast but error-prone.
2. Brute-force enumeration with 5 nested loops – reliable for 20 players.

Implementation:

public class Main {
    public static void main(String[] args) {
        int[] pos1 = {97, 92, 0, 0, 89, 82, 0, 0, 0, 95, 0, 0, 94, 0, 0, 0, 98, 93, 0, 0};
        int[] pos2 = {90, 85, 0, 0, 83, 86, 0, 97, 0, 99, 0, 0, 91, 83, 0, 0, 83, 87, 0, 99};
        int[] pos3 = {0, 96, 0, 0, 97, 0, 0, 96, 89, 0, 96, 0, 0, 87, 98, 0, 99, 92, 0, 96};
        int[] pos4 = {0, 0, 0, 80, 0, 0, 87, 0, 0, 0, 97, 93, 0, 0, 97, 93, 98, 96, 89, 95};
        int[] pos5 = {0, 0, 93, 86, 0, 0, 90, 0, 0, 0, 0, 98, 0, 0, 98, 86, 81, 98, 92, 81};
        int maxScore = 0;
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 20; j++) {
                for (int k = 0; k < 20; k++) {
                    for (int l = 0; l < 20; l++) {
                        for (int m = 0; m < 20; m++) {
                            if (i != j && i != k && i != l && i != m &&
                                j != k && j != l && j != m &&
                                k != l && k != m &&
                                l != m) {
                                int sum = pos1[i] + pos2[j] + pos3[k] + pos4[l] + pos5[m];
                                if (sum > maxScore) maxScore = sum;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(maxScore); // 490 (example)
    }
}

---

Problem B: Distinct Substrings (5/5)

Count the number of distinct non-empty substrings of the string "0100110001010001".

Solution 1: Use ArrayList and manual duplicate check.

Solution 2: Use HashSet for automatic deduplication.

Implementation (HashSet):

import java.util.HashSet;
import java.util.Set;

public class SubstringCounter {
    public static void main(String[] args) {
        String s = "0100110001010001";
        Set<String> unique = new HashSet<>();
        for (int start = 0; start < s.length(); start++) {
            for (int end = start + 1; end <= s.length(); end++) {
                unique.add(s.substring(start, end));
            }
        }
        System.out.println(unique.size());
    }
}

---

Problem C: Sequence Evaluation (10/10)

A sequence starts with 1, 1, 1, and each subsequent term is the sum of the previous three. Find the last 4 digits of the 20190324th term.

Idea: Use iterative addition modulo 10000 to avoid huge numbers.

public class LastFourDigits {
    public static void main(String[] args) {
        int a = 1, b = 1, c = 1, d = 0;
        for (int i = 4; i <= 20190324; i++) {
            d = (a + b + c) % 10000;
            a = b;
            b = c;
            c = d;
        }
        System.out.println(d); // 4659
    }
}

---

Problem D: Decomposition of 2019 (10/10)

Decompose 2019 into three distinct positive integers, none of which contain digits 2 or 4. Count the number of unordered triples.

Approach: Iterate over two numbers and compute the third, then check conditions and uniqueness.

public class DecompositionCount {
    public static void main(String[] args) {
        int count = 0;
        for (int x = 1; x < 2019; x++) {
            if (containsBadDigit(x)) continue;
            for (int y = x + 1; y < 2019 - x - y; y++) {
                int z = 2019 - x - y;
                if (z <= y) continue; // enforce x < y < z
                if (containsBadDigit(y) || containsBadDigit(z)) continue;
                count++;
            }
        }
        System.out.println(count); // 40785
    }

    static boolean containsBadDigit(int n) {
        while (n > 0) {
            int digit = n % 10;
            if (digit == 2 || digit == 4) return true;
            n /= 10;
        }
        return false;
    }
}

---

Problem E: Maze (0/15 – no code attempted)

Given a 30x50 binary maze (0 = open, 1 = wall), find the shortest path from top-left to bottom-right. Among shortest paths, choose the lexicographically smallest sequence of moves (D: down, U: up, L: left, R: right).

Typical solution: Breadth-First Search (BFS) from start, recoridng predecessor and move string. Since we need lexicographically smallest, we can explore directions in order D, L, R, U (or D, R, L, U, but careful with priority). Because BFS guarantees shortest path, and exploring in lexicographic order of moves ensures the first found path is smallest.

No code submitted in the original solution.

---

Problem F: Sum of Special Numbers (15/15)

Find the sum of all numbers from 1 to n that contain at least one of the digits 2, 0, 1, or 9 (ignoring leading zeros).

import java.util.Scanner;

public class SpecialSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long total = 0;
        for (int i = 1; i <= n; i++) {
            if (isMatch(i)) total += i;
        }
        System.out.println(total);
        sc.close();
    }

    static boolean isMatch(int num) {
        String s = Integer.toString(num);
        for (char c : s.toCharArray()) {
            if (c == '2' || c == '1' || c == '9' || c == '0') return true;
        }
        return false;
    }
}

---

Problem G: Delivery Priority (18/20 partial)

We have N shops with initial priority 0. At each time unit, if a shop receives an order, its priority increases by 2 per order; otherwise it decreases by 1 (minimum 0). When priority > 5, the shop enters the "priority cache"; when priority ≤ 3, it leaves. Given M orders (time, ID) and total time T, count how many shops are in the cache at time T.

Implementation (optimized with events):

import java.util.*;

public class ShopCache {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();
        Map<Integer, List<Integer>> orders = new HashMap<>();
        for (int i = 0; i < M; i++) {
            int ts = sc.nextInt();
            int id = sc.nextInt();
            orders.computeIfAbsent(id, k -> new ArrayList<>()).add(ts);
        }
        int inCache = 0;
        for (int id = 1; id <= N; id++) {
            List<Integer> times = orders.getOrDefault(id, new ArrayList<>());
            Collections.sort(times);
            int priority = 0;
            int lastTime = 0;
            boolean inside = false;
            int idx = 0;
            for (int t = 1; t <= T; t++) {
                // process orders at this time
                while (idx < times.size() && times.get(idx) == t) {
                    priority += 2;
                    idx++;
                }
                // decrease if no order
                if (idx == 0 || t > times.get(idx-1)) {
                    priority = Math.max(0, priority - 1);
                }
                if (priority > 5 && !inside) {
                    inside = true;
                    inCache++;
                } else if (priority <= 3 && inside) {
                    inside = false;
                    inCache--;
                }
            }
        }
        System.out.println(inCache);
        sc.close();
    }
}

Note: The original code achieved 90% score; a more efficient approach sorts orders and processes per shop.

---

Problem H: Character Relevance Analysis (0/20)

Given integer K and a text string (up to 1,000,000 characters), count how many times "Alice" and "Bob" appear as separate words within K characters of each other. Words are case-sensitive; punctuation allowed, but no adjacent letters.

Idea: Locate all indices where "Alice" and "Bob" occur. For each occurrence pair, check if the distance (number of characters between the end of the first word and the start of the second, or vice versa) ≤ K. Use two lists and two-pointer technique for O(n) complexity.

No code supplied.

---

Problem I: Suffix Expression (0/25)

Given N plus signs, M minus signs, and N+M+1 integers, arrange them into a legal suffix expression to maximize the result. Equivalent to choosing a parenthesization with the given operators. The problem reduces to: we can essentially choose which numbers get positive and which negative, except at least one number must be positive and one negative (due to the nature of suffix expressions). The maximum sum is achieved by taking the sum of absolute values of all numbers, then adjusting based on the sign of the smallest/largest.

Algorithm: Sort the numbers. If all numbers are non-negative and there is at least one minus sign, then we must subtract the smallest value twice? Actually, analysis shows: if there is at least one minus, we can flip signs arbitrarily except that we cannot make all numbers positive. The maximum is sum of absolute values, but then we need to subtract 2 * min(|min|) if all number have the same sign? This problem is known: answer = sum of absolute values - (if M > 0 and all numbers positive) subtract 2*min; else if M > 0 and all negative, add 2*max? A precise solution exists.

No code provided.

---

Problem J: Mental Energy Transfer (0/25)

We have n High Templars with initial energies ai. Operation: choose i in [2,n-1]; if ai ≥ 0, then ai-1 += ai, ai+1 += ai, ai -= 2ai; if ai < 0, similar but sign flips. Goal: minimize max |ai| after any number of operations. This is equivalent to allowing arbitrary transfers among adjacent positions while preserving total sum? Actually the operation preserves sum but shifts energy outward. The problem reduces to finding an arrangement of the prefix sum differences? Known solution: work with prefix sums and sort, then compute minimum possible maximum absolute difference.

No code provided.

---

Total score: 53