Problem 1: Dumpling Purchase Optimization

The problem reduces to a daily deciison: buy dumplings at the current price or rely on an earlier purchase plus storage cost. The total expense for day i if we buy on day j ≤ i is price[j] + c*(i - j). This can be rewritten as (price[j] - c*j) + c*i. Thus we can maintain the minimum value of price[j] - c*j seen so far; let this be base_min. Each day we add base_min + c*i to the total cost.

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

int main() {
    int n;
    long long c;
    cin >> n >> c;
    vector<long long> price(n);
    for (int i = 0; i < n; ++i) cin >> price[i];

    long long best = price[0] - c;   // minimum (price[j] - c*j) seen so far
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        best = min(best, price[i] - c * i);
        total += best + c * i;
    }
    cout << total << "\n";
    return 0;
}

Problem 2: Pizza Cutting – Maximum Angle Gap

We track the cumulative rotation angle modulo 360. Every cut location (including 0° and 360°) is marked. The largest gap between two consecutive cut positions is the answer.

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

int main() {
    int n;
    cin >> n;
    vector<bool> cut(361, false);
    cut[0] = cut[360] = true;
    int angle = 0;
    for (int i = 0; i < n; ++i) {
        int step;
        cin >> step;
        angle = (angle + step) % 360;
        cut[angle] = true;
    }
    int last = 0, best_gap = 0;
    for (int deg = 1; deg <= 360; ++deg) {
        if (cut[deg]) {
            best_gap = max(best_gap, deg - last);
            last = deg;
        }
    }
    cout << best_gap << "\n";
    return 0;
}

Problem 3: Memory Fragments from Color Blocks

Process consecutive segments of identical colors. For a run of length len, you can perform at most min(m, (len-1)/2) operations, each grenting 2 fragments. Update the answer and remaining operations. If k ≠ 2 and len is even, an extra fragment can be earned later (count them as extra_ops). After scanning all segments, add min(m, extra_ops) to the answer.

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

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> colors(n+2);
    for (int i = 1; i <= n; ++i) cin >> colors[i];
    colors[n+1] = k + 1;   // sentinel

    int run = 0, ans = 0, extra = 0;
    for (int i = 1; i <= n+1; ++i) {
        if (i == 1 || colors[i] == colors[i-1]) {
            ++run;
        } else {
            ++ans;                          // base fragment for the segment change
            int ops = min(m, (run - 1) / 2);
            ans += ops * 2;
            m -= ops;
            if (k != 2 && run % 2 == 0) ++extra;
            run = 1;
        }
    }
    cout << ans + min(m, extra) << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Problem 4: Tasty Food with Poison Rules

Maintain two DP states: healthy[i] – maximum tastiness up to day i ending in a healthy state, and poisoned[i] – maximum tastiness ending in a poisoned state. A poisonous meal (op = 1) can only be eaten from the healthy state. A safe meal (op = 0) can be eaten from either state.

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

int main() {
    int n;
    cin >> n;
    vector<long long> healthy(n+1, 0), poisoned(n+1, 0);
    for (int i = 1; i <= n; ++i) {
        int is_poison;
        long long taste;
        cin >> is_poison >> taste;
        healthy[i] = healthy[i-1];
        poisoned[i] = poisoned[i-1];
        if (is_poison) {
            poisoned[i] = max(poisoned[i], healthy[i-1] + taste);
        } else {
            healthy[i] = max(healthy[i], max(healthy[i-1], poisoned[i-1]) + taste);
        }
    }
    cout << max(healthy[n], poisoned[n]) << "\n";
    return 0;
}

Problem 5: Alchemy – Number of Shortest Paths

Build an undirected graph where vertices represent alchemical steps and edges represent direct dependencies. Perform a BFS from vertex 1 to compute the number of shortest paths to each vertex, modulo 10^9+7.

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

const int MOD = 1'000'000'007;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dist(n+1, 0);
    vector<long long> ways(n+1, 0);
    vector<int> state(n+1, 0); // 0 = unseen, 1 = in queue, 2 = processed
    queue<int> q;
    q.push(1);
    ways[1] = 1;
    state[1] = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        state[u] = 2;
        for (int v : adj[u]) {
            if (dist[v] == 0 && v != 1) {
                dist[v] = dist[u] + 1;
            }
            if (state[v] != 2 && dist[v] == dist[u] + 1) {
                ways[v] = (ways[v] + ways[u]) % MOD;
                if (state[v] == 0) {
                    state[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    cout << ways[n] << "\n";
    return 0;
}