Fountain Construction Optimization

Three construction strategies exist: using only coins, only diamonds, or a combination. Iterate through coin-based fountains while tracking maximum aesthetic value achievable with remaining coins via a segment tree. Similarly process diamond-based options and update combined solutions during iteration.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

template<typename T>
class SegmentTree {
public:
    struct Node { ll L, R, MaxVal; };
    vector<Node> tree;
    int size;

    SegmentTree(int n) : size(n) {
        tree.resize(n * 4);
        build(1, 1, n);
    }

    void build(int idx, int left, int right) {
        tree[idx] = {left, right, 0};
        if (left == right) return;
        int mid = (left + right) / 2;
        build(idx*2, left, mid);
        build(idx*2+1, mid+1, right);
    }

    void update(int idx, int pos, ll value) {
        if (tree[idx].L == tree[idx].R) {
            tree[idx].MaxVal = max(tree[idx].MaxVal, value);
            return;
        }
        int mid = (tree[idx].L + tree[idx].R) / 2;
        if (pos <= mid) update(idx*2, pos, value);
        else update(idx*2+1, pos, value);
        tree[idx].MaxVal = max(tree[idx*2].MaxVal, tree[idx*2+1].MaxVal);
    }

    ll query(int idx, int ql, int qr) {
        if (ql <= tree[idx].L && tree[idx].R <= qr) 
            return tree[idx].MaxVal;
        int mid = (tree[idx].L + tree[idx].R) / 2;
        if (qr <= mid) return query(idx*2, ql, qr);
        if (ql > mid) return query(idx*2+1, ql, qr);
        return max(query(idx*2, ql, qr), query(idx*2+1, ql, qr));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, coinMax, diamondMax;
    cin >> n >> coinMax >> diamondMax;
    
    vector<vector<pair<int, int>>> materials(2);
    for (int i = 0; i < n; i++) {
        int beauty, price;
        char type;
        cin >> beauty >> price >> type;
        materials[type-'C'].push_back({beauty, price});
    }

    SegmentTree<ll> coinTree(coinMax), diamondTree(diamondMax);
    int result = 0;
    
    for (auto [val, cost] : materials[0]) {
        if (coinMax >= cost) {
            ll remaining = coinMax - cost;
            ll best = (remaining > 0) ? coinTree.query(1, 1, remaining) : 0;
            if (best) result = max(result, val + (int)best);
        }
        coinTree.update(1, cost, val);
    }

    ll coinBest = (coinMax > 0) ? coinTree.query(1, 1, coinMax) : 0;
    for (auto [val, cost] : materials[1]) {
        if (diamondMax >= cost) {
            ll remaining = diamondMax - cost;
            ll best = (remaining > 0) ? diamondTree.query(1, 1, remaining) : 0;
            if (best || coinBest) 
                result = max(result, val + (int)max(best, coinBest));
        }
        diamondTree.update(1, cost, val);
    }

    cout << result << '\n';
    return 0;
}

Same Differences Counting

Transform the condition a_j - a_i = j - i into a_i - i = a_j - j. Maintain frequency counts of a_i - i values during iteration to efficiently compute valid pairs.

#include <iostream>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int n;
        cin >> n;
        map<int, long long> freq;
        long long total = 0;
        
        for (int idx = 1; idx <= n; idx++) {
            int num;
            cin >> num;
            total += freq[num - idx];
            freq[num - idx]++;
        }
        cout << total << '\n';
    }
    return 0;
}

Lexicographical Order Validation

Establish character precedence relationships from adjacent string comparisons. Perform topological sorting to determine valid alphabet ordering, detecting cycles for invalid cases.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<string> words(n);
    for (auto &w : words) cin >> w;
    
    vector<vector<int>> graph(26);
    vector<int> inDegree(26, 0);
    set<string> prefixes;
    
    for (auto &w : words) {
        if (prefixes.count(w)) {
            cout << "Impossible\n";
            return 0;
        }
        for (int len = 1; len <= w.size(); len++) 
            prefixes.insert(w.substr(0, len));
    }

    for (int i = 0; i < n-1; i++) {
        for (int pos = 0; pos < words[i].size(); pos++) {
            if (pos >= words[i+1].size()) {
                cout << "Impossible\n";
                return 0;
            }
            if (words[i][pos] != words[i+1][pos]) {
                int from = words[i][pos] - 'a';
                int to = words[i+1][pos] - 'a';
                graph[from].push_back(to);
                inDegree[to]++;
                break;
            }
        }
    }

    queue<int> process;
    vector<int> sorted;
    for (int i = 0; i < 26; i++) 
        if (!inDegree[i]) process.push(i);
    
    while (!process.empty()) {
        int cur = process.front();
        process.pop();
        sorted.push_back(cur);
        for (int neighbor : graph[cur]) {
            if (--inDegree[neighbor] == 0) 
                process.push(neighbor);
        }
    }

    if (sorted.size() != 26) cout << "Impossible\n";
    else {
        for (int c : sorted) cout << (char)(c + 'a');
    }
    return 0;
}

Nearest Valid House Search

Iterate through house positions, computing minimum distance from target position to houses meeting cost constraints.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int houses, target, maxCost;
    cin >> houses >> target >> maxCost;
    vector<int> costs(houses + 1);
    
    for (int i = 1; i <= houses; i++) 
        cin >> costs[i];
    
    long minDist = houses * 10;
    for (int pos = 1; pos <= houses; pos++) {
        if (costs[pos] && costs[pos] <= maxCost) 
            minDist = min(minDist, abs(pos - target) * 10L);
    }
    cout << minDist << '\n';
    return 0;
}

Array Partition Validation

Discretize array values and count contiguous increasing sequences. Verify if the count of sequences is within the allowed partition limit.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    for (int i = 0; i < n; i++) 
        arr[i] = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin();
    
    int segments = 0;
    for (int i = 0; i < n; ) {
        int j = i;
        while (j+1 < n && arr[j+1] == arr[j] + 1) j++;
        segments++;
        i = j + 1;
    }
    cout << (segments <= k ? "Yes" : "No") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tests;
    cin >> tests;
    while (tests--) solve();
    return 0;
}

Threshold Achievement Detection

Maintain maximum prefix sums using segment trees to efficiently determine when cumulative values exceed dynamic thresholds.

#include <iostream>
#include <vector>
#include <functional>
#include <iomanip>
using namespace std;
using ll = long long;

struct SegNode { ll L, R, PrefixMax, Total; };

class PrefixSumTree {
    vector<SegNode> data;
    int size;

    void combine(SegNode &parent, SegNode &left, SegNode &right) {
        parent.Total = left.Total + right.Total;
        parent.PrefixMax = max(left.PrefixMax, left.Total + right.PrefixMax);
    }

public:
    PrefixSumTree(vector<int> base) : size(base.size()-1) {
        data.resize(4 * size);
        function<void(int, int, int)> build = [&](int idx, int l, int r) {
            data[idx] = {l, r, 0, 0};
            if (l == r) {
                data[idx] = {l, r, base[l], base[l]};
                return;
            }
            int mid = (l + r) / 2;
            build(idx*2, l, mid);
            build(idx*2+1, mid+1, r);
            combine(data[idx], data[idx*2], data[idx*2+1]);
        };
        build(1, 1, size);
    }

    void modify(int idx, int pos, int value) {
        if (data[idx].L == data[idx].R) {
            data[idx].Total = value;
            data[idx].PrefixMax = value;
            return;
        }
        int mid = (data[idx].L + data[idx].R) / 2;
        if (pos <= mid) modify(idx*2, pos, value);
        else modify(idx*2+1, pos, value);
        combine(data[idx], data[idx*2], data[idx*2+1]);
    }

    SegNode findThreshold(int idx, ll current, ll threshold) {
        if (data[idx].L == data[idx].R) 
            return {0,0, current + data[idx].PrefixMax, 0};
        
        if (current + data[idx*2].PrefixMax >= threshold)
            return findThreshold(idx*2, current, threshold);
        else
            return findThreshold(idx*2+1, current + data[idx*2].Total, threshold);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, queries;
    cin >> n >> k >> queries;
    vector<int> base(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> base[i];
        base[i] -= k;
    }

    PrefixSumTree tree(base);
    while (queries--) {
        int pos, value;
        cin >> pos >> value;
        tree.modify(1, pos, value - k);
        auto res = tree.findThreshold(1, 0, 0);
        double result = k + static_cast<double>(res.PrefixMax) / res.L;
        cout << fixed << setprecision(15) << result << '\n';
    }
    return 0;
}

Digit Separation Scheme

Separate digits into odd and even positions, interpret as distinct numbers, and compute valid combination count.

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tests;
    cin >> tests;
    while (tests--) {
        string num;
        cin >> num;
        long odd = 0, even = 0;
        
        for (int i = 0; i < num.size(); i++) {
            if (i % 2 == 0) even = even * 10 + (num[i] - '0');
            else odd = odd * 10 + (num[i] - '0');
        }
        cout << (odd + 1) * (even + 1) - 2 << '\n';
    }
    return 0;
}

Multidimensional Resource Allocation

Implement dynamic programming with multiple constraints to determine minimum cost for achieving multidimensional resource thresholds.

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

const long long INF = 9e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int items, dims, target;
    cin >> items >> dims >> target;
    vector<int> thresholds(5, target);
    long dp[7][7][7][7][7];
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0][0][0] = 0;
    
    for (int i = 1; i <= items; i++) {
        int cost;
        cin >> cost;
        vector<int> vals(5,0);
        for (int d = 0; d < dims; d++) cin >> vals[d];
        
        for (int d1 = thresholds[0]; d1 >= 0; d1--)
        for (int d2 = thresholds[1]; d2 >= 0; d2--)
        for (int d3 = thresholds[2]; d3 >= 0; d3--)
        for (int d4 = thresholds[3]; d4 >= 0; d4--)
        for (int d5 = thresholds[4]; d5 >= 0; d5--) {
            int nd1 = min(d1 + vals[0], thresholds[0]);
            int nd2 = min(d2 + vals[1], thresholds[1]);
            int nd3 = min(d3 + vals[2], thresholds[2]);
            int nd4 = min(d4 + vals[3], thresholds[3]);
            int nd5 = min(d5 + vals[4], thresholds[4]);
            dp[nd1][nd2][nd3][nd4][nd5] = min(
                dp[nd1][nd2][nd3][nd4][nd5],
                dp[d1][d2][d3][d4][d5] + cost
            );
        }
    }
    
    long result = dp[target][target][target][target][target];
    if (result > INF/2) cout << -1 << '\n';
    else cout << result << '\n';
    return 0;
}

Arithmetic Sequence Validation

Analyze sorted sequence differences to identify removable elements that would restore arithmetic progression properties.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    if (n < 4) {
        cout << "1\n";
        return 0;
    }

    vector<pair<ll, int>> items(n);
    for (int i = 0; i < n; i++) {
        cin >> items[i].first;
        items[i].second = i+1;
    }
    sort(items.begin(), items.end());

    multiset<ll> intervals;
    for (int i = 2; i < n-1; i++)
        intervals.insert(items[i].first - items[i-1].first);

    ll firstDiff = items[1].first - items[0].first;
    ll lastDiff = items[n-1].first - items[n-2].first;
    
    if (intervals.size() && *intervals.begin() == *intervals.rbegin()) {
        if (firstDiff == *intervals.begin()) {
            cout << items[n-1].second << '\n';
            return 0;
        }
        else if (lastDiff == *intervals.begin()) {
            cout << items[0].second << '\n';
            return 0;
        }
    }

    intervals.insert(firstDiff);
    intervals.insert(lastDiff);
    
    for (int i = 1; i < n-1; i++) {
        ll prevDiff = items[i].first - items[i-1].first;
        ll nextDiff = items[i+1].first - items[i].first;
        ll merged = items[i+1].first - items[i-1].first;
        
        intervals.erase(intervals.find(prevDiff));
        intervals.erase(intervals.find(nextDiff));
        intervals.insert(merged);
        
        if (*intervals.begin() == *intervals.rbegin()) {
            cout << items[i].second << '\n';
            return 0;
        }
        
        intervals.erase(intervals.find(merged));
        intervals.insert(prevDiff);
        intervals.insert(nextDiff);
    }
    cout << "-1\n";
    return 0;
}

Time-Based Path Optimization

Utilize Dijkstra's algorithm with time-event tracking to compute earliest arrival times through temporally constrained paths.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

vector<vector<int>> timeEvents;

class TimeGraph {
    vector<vector<pair<int, int>>> adj;
    vector<ll> arrival;
    int nodes;

public:
    TimeGraph(int n) : nodes(n) {
        adj.resize(n+1);
        arrival.assign(n+1, -1);
    }

    void addEdge(int u, int v, int edgeType) {
        adj[u].push_back({v, edgeType});
        adj[v].push_back({u, edgeType});
    }

    void computePaths(int start) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        pq.push({0, start});
        
        while (!pq.empty()) {
            auto [time, node] = pq.top();
            pq.pop();
            if (arrival[node] != -1) continue;
            arrival[node] = time;
            
            for (auto [neighbor, type] : adj[node]) {
                auto it = lower_bound(timeEvents[type].begin(), timeEvents[type].end(), time);
                if (it != timeEvents[type].end()) 
                    pq.push({*it + 1, neighbor});
            }
        }
    }

    ll getTime(int node) { return arrival[node]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int nodes, edgeTypes;
    cin >> nodes >> edgeTypes;
    TimeGraph graph(nodes);
    timeEvents.resize(edgeTypes+1);
    
    for (int type = 1; type <= edgeTypes; type++) {
        int count;
        cin >> count;
        while (count--) {
            int u, v;
            cin >> u >> v;
            graph.addEdge(u, v, type);
        }
    }

    int eventCount;
    cin >> eventCount;
    for (int i = 0; i < eventCount; i++) {
        int type;
        cin >> type;
        timeEvents[type].push_back(i);
    }

    graph.computePaths(1);
    cout << graph.getTime(nodes) << '\n';
    return 0;
}

Triangle Formation Game

Apply game theory analysis to determine winning positions based on transformed state values and XOR properties.

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tests;
    cin >> tests;
    while (tests--) {
        int a, b, c;
        cin >> a >> b >> c;
        cout << ((a-1) ^ (b-1) ^ (c-1) ? "Win" : "Lose") << '\n';
    }
    return 0;
}

Mouse Survival Probability

Compute survival probabilities through dynamic programming states representing remaining mice counts and transition probabilities.

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int white, black;
    cin >> white >> black;
    vector<vector<double>> dp(white+1, vector<double>(black+1, 0));
    
    for (int w = 1; w <= white; w++) {
        dp[w][0] = 1.0;
        if (black >= 1) 
            dp[w][1] = (double)w / (w+1);
    }

    for (int w = 1; w <= white; w++) {
        for (int b = 2; b <= black; b++) {
            dp[w][b] = (double)w / (w+b);
            double blackDraw = (double)b / (w+b);
            double secondBlack = (double)(b-1) / (w+b-1);
            
            if (b >= 2) {
                double whiteEscape = (double)w / (w+b-2);
                dp[w][b] += blackDraw * secondBlack * whiteEscape * dp[w-1][b-2];
            }
            if (b >= 3) {
                double blackEscape = (double)(b-2) / (w+b-2);
                dp[w][b] += blackDraw * secondBlack * blackEscape * dp[w][b-3];
            }
        }
    }
    cout << fixed << setprecision(10) << dp[white][black] << '\n';
    return 0;
}