Greeting Code

#include <iostream>
int main() {
    std::cout << "Competition Day!" << '\n';
    return 0;
}

Neighbor Sum Array

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int len;
    cin >> len;
    vector<int> data(len);
    for (int i = 0; i < len; ++i) {
        cin >> data[i];
    }
    for (int i = 0; i < len; ++i) {
        int left = (i - 1 + len) % len;
        int right = (i + 1) % len;
        cout << data[left] + data[right] << ' ';
    }
    return 0;
}

Absolute Value Summation

For an array of any length, converting all elements to positive requires at most length operations. The final result is simply the sum of absolute values of all element.

#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ll total = 0;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        total += llabs(nums[i]);
    }
    cout << total << '\n';
    return 0;
}

Check Consecutive Odd Square Difference

Take an odd integer a, the difference between a² and (a-2)² expands to 8*(a-1)/2, which is a multiple of 8. Handle zero input separately.

#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 num;
        cin >> num;
        ll candidate = (num / 4) + 1;
        if (num % 4 == 0 && candidate % 2 == 1 && candidate - 2 > 0) {
            cout << "Yes\n" << candidate - 2 << ' ' << candidate << '\n';
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

Maximum Valid Pairs for Isosceles Triangle

Sort both input arrays, then use a two-pointer approach starting from the end. If twice the current element from the first array is greater than or equal to the current element from the second array, count a valid pair and move both pointers left; otherwise, only move the second pointer.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin >> count;
    vector<int> first(count), second(count);
    for (int i = 0; i < count; ++i) {
        cin >> first[i];
    }
    for (int i = 0; i < count; ++i) {
        cin >> second[i];
    }
    sort(first.begin(), first.end());
    sort(second.begin(), second.end());
    int ptr1 = count - 1, ptr2 = count - 1, result = 0;
    while (ptr1 >= 0 && ptr2 >= 0) {
        if (first[ptr1] * 2 >= second[ptr2]) {
            result++;
            ptr1--;
            ptr2--;
        } else {
            ptr2--;
        }
    }
    cout << result << '\n';
    return 0;
}

Solve Square Root Plus Logarithm Equation

Compute log_k x using natural logarithm division: log(x)/log(k). Use binary search to find the minimal integer x satisfying the equation.

#include <iostream>
#include <cmath>
using namespace std;
int base, target;
bool isSufficient(long long x) {
    double root = sqrt(x);
    int log_val = static_cast<int>(log(x) / log(base));
    return root + log_val >= target;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        cin >> base >> target;
        long long left = 1, right = 1e18;
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (isSufficient(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        cout << left << '\n';
    }
    return 0;
}

Count Numbers with Exact Closed Shapes in Range

Use digit dynamic programming to solve this range query problem. Precompute dp[pos][cnt] which represents the number of pos-digit numbers (including leading zeros) with exactly cnt closed shapes. The closed shape counts for digits 0-9 are [1,0,0,0,1,0,1,0,2,1].

To calculate the count up to a number x, convert x into a digit vector, then process each digit from most significant to least: for each position, consider all valid digits less than the current digit, add the precomputed dp values for remaining positions, then subtract the closed shape count of the current digit and proceed. Also add counts of numbers with fewer digits than x. Finallly, check if x itself meets the requirement.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int closed_shapes[] = {1,0,0,0,1,0,1,0,2,1};
ll dp[15][25];
ll compute(ll x, ll k) {
    if (x == 0) {
        return (k == closed_shapes[0]) ? 1 : 0;
    }
    vector<int> digits;
    while (x > 0) {
        digits.push_back(x % 10);
        x /= 10;
    }
    reverse(digits.begin(), digits.end());
    ll res = 0, current_cnt = k;
    int self_cnt = 0;
    int n = digits.size();
    for (int i = 1; i < n; ++i) {
        for (int d = 1; d <= 9; ++d) {
            if (current_cnt >= closed_shapes[d]) {
                res += dp[i-1][current_cnt - closed_shapes[d]];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int upper = digits[i];
        int start = (i == 0) ? 1 : 0;
        for (int d = start; d < upper; ++d) {
            if (current_cnt >= closed_shapes[d]) {
                res += dp[n - i - 1][current_cnt - closed_shapes[d]];
            }
        }
        self_cnt += closed_shapes[upper];
        if (self_cnt > current_cnt) {
            break;
        }
        current_cnt -= closed_shapes[upper];
    }
    if (self_cnt == k) {
        res++;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    dp[0][0] = 1;
    for (int pos = 1; pos <= 12; ++pos) {
        for (int cnt = 0; cnt <= 24; ++cnt) {
            for (int d = 0; d <= 9; ++d) {
                if (cnt >= closed_shapes[d]) {
                    dp[pos][cnt] += dp[pos-1][cnt - closed_shapes[d]];
                }
            }
        }
    }
    ll L, R, K;
    cin >> L >> R >> K;
    cout << compute(R, K) - compute(L-1, K) << '\n';
    return 0;
}

Segment Tree for Max and Second Max with Game Theory

Use a segment tree to maintain the maximum and second maximum values of any interval. After processing all queries, sum these two values from each query result. Acording to Bash Game, if the total sum is divisible by m+1, the second player wins; otherwise, the first player wins.

To merge two child nodes into a parent node: the parent's maximum is the larger of the two children's maxima, and the parent's second maximum is the larger of the smaller of the two children's maxima and the maximum of the two children's second maxima.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct Node {
    int l, r;
    int max1, max2;
};
vector<Node> tree;
vector<int> arr;
void pushUp(int u) {
    int left = u << 1;
    int right = u << 1 | 1;
    tree[u].max1 = max(tree[left].max1, tree[right].max1);
    tree[u].max2 = max(min(tree[left].max1, tree[right].max1), max(tree[left].max2, tree[right].max2));
}
void build(int u, int l, int r) {
    tree[u].l = l;
    tree[u].r = r;
    if (l == r) {
        tree[u].max1 = arr[l];
        tree[u].max2 = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushUp(u);
}
pii query(int u, int l, int r) {
    if (tree[u].l >= l && tree[u].r <= r) {
        return {tree[u].max1, tree[u].max2};
    }
    int mid = (tree[u].l + tree[u].r) >> 1;
    pii leftRes = {0, 0}, rightRes = {0, 0};
    if (l <= mid) {
        leftRes = query(u << 1, l, r);
    }
    if (r > mid) {
        rightRes = query(u << 1 | 1, l, r);
    }
    int mergedMax1 = max(leftRes.first, rightRes.first);
    int mergedMax2 = max(min(leftRes.first, rightRes.first), max(leftRes.second, rightRes.second));
    return {mergedMax1, mergedMax2};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    arr.resize(n + 1);
    tree.resize(4 * n);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    build(1, 1, n);
    ll total = 0;
    while (q--) {
        int L, R;
        cin >> L >> R;
        pii res = query(1, L, R);
        total += res.first + res.second;
    }
    int m;
    cin >> m;
    cout << total << '\n';
    cout << (total % (m + 1) != 0 ? "red" : "blue") << '\n';
    return 0;
}