Sexagenary Cycle Offset Calculation

Converting between Chinese sexagenary cycle notation and absolute year values involves identifying positions with in the 60-year cycle. The cycle combines ten celestial stems with twelve terrestrial branches. Given a target designation composed of one stem and one branch, the corresponding Gregorian year offset can be computed by establishing the positional mapping.

Instead of decomposing the string from the end, we can match the input against predefined sequences. The stems cycle every 10 years while branches cycle every 12 years. The alignment creates a 60-year period. By determining the index of the stem (0-9) and branch (0-11), we calculate the offset within the cycle using the relationship between these modular systems.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<string> stems = {"jia", "yi", "bing", "ding", "wu", "ji", "geng", "xin", "ren", "gui"};
    vector<string> branches = {"zi", "chou", "yin", "mao", "chen", "si", "wu", "wei", "shen", "you", "xu", "hai"};
    
    unordered_map<string, int> stemIdx, branchIdx;
    for (int i = 0; i < 10; i++) stemIdx[stems[i]] = i;
    for (int i = 0; i < 12; i++) branchIdx[branches[i]] = i;
    
    int cases;
    cin >> cases;
    while (cases--) {
        string input;
        cin >> input;
        
        string br, st;
        for (int len = 3; len >= 2; len--) {
            if (input.length() < len) continue;
            string suffix = input.substr(input.length() - len);
            if (branchIdx.count(suffix)) {
                br = suffix;
                st = input.substr(0, input.length() - len);
                break;
            }
        }
        
        int s = stemIdx[st];
        int b = branchIdx[br];
        
        int offset = s;
        while (offset % 12 != b) {
            offset += 10;
        }
        
        cout << 1984 + offset << '\n';
    }
    return 0;
}

Constrained Longest Increasing Subsequence

When processing repeated concatenations of a string template, the longest strictly increasing subsequence (LIS) length is bounded by the aplhabet size. With lowercase English letters, the maximum possible LIS is 26, regardless of repetition count k.

For inputs where k may contain up to 100 digits, parse the value as a string and cap it at 26. Construct the repeated sequence up to this limit, then apply standard LIS dynamic programming. The O(n²) approach suffices given the bounded output length (maximum 26 × |template|).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        string pattern, kStr;
        cin >> pattern >> kStr;
        
        int repeat;
        if (kStr.length() > 2) {
            repeat = 26;
        } else {
            repeat = stoi(kStr);
            repeat = min(repeat, 26);
        }
        
        string sequence;
        for (int i = 0; i < repeat; i++) {
            sequence += pattern;
        }
        
        int n = sequence.length();
        vector<int> dp(n, 1);
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (sequence[j] < sequence[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        
        cout << maxLen << '\n';
    }
    return 0;
}

Quadruple Enumeration with Zero Separation

Counting valid quadruples (p, 0, p, q) in an array requires efficient tracking of element positions. A brute-force approach is infeasible for large inputs. Instead, preprocess three auxiliary structures:

1. First occurrence tracker: Records the initial index of each distinct non-zero value.
2. Nearest zero prefix: For each position, stores the index of the closest preceding zero.
3. Suffix distinct counter: Calculates how many unique non-zero values exist from each position to the array end.

For each element at index i serving as the second p in the pattern, check if its first occurrence appears before the nearest zero. If valid, add the suffix distinct count at i to the total. To prevent double-counting identical p values, invalidate the first occurrence tracker after processing.

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

const ll LARGE = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        vector<ll> values(n);
        for (int i = 0; i < n; i++) cin >> values[i];
        
        vector<ll> firstPos(1000005, -1);
        vector<int> lastZero(n);
        vector<int> suffixUnique(n);
        
        int lastZ = -1;
        for (int i = 0; i < n; i++) {
            if (values[i] == 0) lastZ = i;
            lastZero[i] = lastZ;
            if (values[i] != 0 && firstPos[values[i]] == -1) {
                firstPos[values[i]] = i;
            }
        }
        
        unordered_set<ll> seen;
        for (int i = n - 1; i >= 0; i--) {
            suffixUnique[i] = seen.size();
            if (values[i] != 0) seen.insert(values[i]);
        }
        
        ll result = 0;
        for (int i = 0; i < n; i++) {
            ll val = values[i];
            if (val == 0) continue;
            if (firstPos[val] < lastZero[i]) {
                result += suffixUnique[i];
                firstPos[val] = LARGE;
            }
        }
        
        cout << result << '\n';
    }
    return 0;
}

Perpendicular Line Counting in Regular Divisions

Given n lines generated by a regular k-sectioned division of the plane, determine how many pairs are perpendicular. Two lines are perpendicular only if the angle between their base orientations is 90 degrees. Since adjacent lines separate by 180/k degrees, perpendicularity requires k to be even (specifically, 90 must be a multiple of 180/k).

For even k, group the lines by their base orientation. There are k/2 distinct orientations. Distribute n lines into these orientations: n % (k/2) groups contain ⌈n/(k/2)⌉ lines, while the rest contain ⌊n/(k/2)⌋ lines.

Within each orientation group, lines are parallel. Perpendicular pairs form between orthogonal orientation groups. For a group with m lines, the number of lines in its perpendicular orientation is determined by the grouping calculation. The total count sums the products of group sizes across perpendicular pairs.

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

ll countPairs(ll m) {
    return (m / 2) * ((m + 1) / 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        ll n, k;
        cin >> n >> k;
        
        if (k % 2 == 1) {
            cout << 0 << '\n';
            continue;
        }
        
        ll groups = k / 2;
        ll base = n / groups;
        ll extra = n % groups;
        
        ll total = extra * countPairs(base + 1) + (groups - extra) * countPairs(base);
        cout << total << '\n';
    }
    return 0;
}

Multi-Resource Takeaway Game

This impartial game involves three resource types: red gems (R), blue gems (B), and magic boxes (M). By assigning weighted values—red=1, blue=2, and box=4—the game reduces to a standard Bash game where players alternately remove 1 to 3 units of total value. The conversion moves (blue→red, box→blue) and direct removal options all result in subtracting 1, 2, or 3 from the total weighted sum.

The total game value calculates as R + 2B + 4M. In standard Bash play with maximum removal 3, positions where the total is divisible by 4 are previous-player wins (P-positions), while non-multiples are next-player wins (N-positions).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        ll red, blue, box;
        cin >> red >> blue >> box;
        
        ll totalValue = red + 2 * blue + 4 * box;
        
        if (totalValue % 4 == 0) {
            cout << "Bob\n";
        } else {
            cout << "Alice\n";
        }
    }
    return 0;
}