Problem A

Problem Statement: Taro avoids stomach illness if he eats food that expired no more then X days ago, and finds unexpired food delicious; expired food beyond X days causes illness. He bought a bag of food today with A days left until expiration and plans to eat it B days later. Determine his state: delicious, safe, or dangerous.

Approach: Calculate remaining days until expiration when eaten: rem_eat = A - B.

• If rem_eat ≥ 0, food is unexpired → delicious.
• Else, check if days expired days_exp = B - A ≤ X → safe.
• Otherwise, dangerous.

int main() { int xp, rem, eat; cin >> xp >> rem >> eat; if (rem - eat >= 0) { cout << "delicious" << endl; } else if (eat - rem <= xp) { cout << "safe" << endl; } else { cout << "dangerous" << endl; } return 0; }

</details>

### Problem B
**Problem Statement:**
There are `N` lights, each with a button. Pressing button `i` turns off light `i` and turns on light `a_i`.
Initially, only light 1 is on. Find the minimum number of button presses to turn on light 2, or output -1 if imposssible.

**Approach:**
Use BFS-like traversal to track visited lights and count presses, leveraging pigeonhole principle to terminate after `N` steps (maximum cycle length).

<details><summary>Show Code</summary>
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> next_light(n + 1);
    vector<bool> visited(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        cin >> next_light[i];
    }
    int current = 1;
    visited[current] = true;
    int count = 0;
    while (true) {
        ++count;
        current = next_light[current];
        if (current == 2 || visited[current]) {
            break;
        }
        visited[current] = true;
    }
    cout << (current == 2 ? count : -1) << endl;
    return 0;
}

Problem C

Problem Statement: Arrange N distinct dogs and M distinct cats in a line such that no two adjacent animals are the same species. Calculate the number of valid permutations modulo 10^9 + 7.

Approach:

• If |N - M| > 1, no valid arrangements (impossible to alternate).
• If N == M, first position has 2 choices (dog or cat), followed by all dogs and cats permuted in their respective positions: 2 * N! * M!.
• If |N - M| == 1, permute all animals in fixed species positions: N! * M!.

Precompute factorials modulo 10^9 + 7 up to 1e5.

const int MOD = 1e9 + 7; const int MAX = 1e5 + 10;

int main() { vector fact(MAX, 1); for (int i = 1; i < MAX; ++i) { fact[i] = fact[i - 1] * i % MOD; } int n, m; cin >> n >> m; if (abs(n - m) > 1) { cout << 0 << endl; } else if (n == m) { cout << 2 * fact[n] % MOD * fact[m] % MOD << endl; } else { cout << fact[n] * fact[m] % MOD << endl; } return 0; }

</details>

### Problem D
**Problem Statement:**
`N` towns lie on a 2D plane, each at `(x_i, y_i)`. The cost to build a road between `(a,b)` and `(c,d)` is `min(|a−c|, |b−d|)`. Find the minimum total cost to connect all towns, modulo `10^9 + 7`.

**Approach:**
Use Kruskal's algorithm for minimum spanning tree (MST), but optimize edge selection. Only conisder adjacent points on sorted x and y axes, reducing edges from `O(N²)` to `O(N)`, making Kruskal's feasible.

<details><summary>Show Code</summary>
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_EDGES = 4e5 + 10;

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
} edges[MAX_EDGES];

int parent[MAX_EDGES];

int find_root(int x) {
    if (parent[x] != x) {
        parent[x] = find_root(parent[x]);
    }
    return parent[x];
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> towns(n + 1, vector<int>(3));  // x, y, index
    for (int i = 1; i <= n; ++i) {
        cin >> towns[i][0] >> towns[i][1];
        towns[i][2] = i;
    }
    int edge_count = 0;
    // Add x-axis adjacent edges
    sort(towns.begin() + 1, towns.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    for (int i = 2; i <= n; ++i) {
        int u = towns[i-1][2];
        int v = towns[i][2];
        int w = towns[i][0] - towns[i-1][0];
        edges[edge_count++] = {u, v, w};
    }
    // Add y-axis adjacent edges
    sort(towns.begin() + 1, towns.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    for (int i = 2; i <= n; ++i) {
        int u = towns[i-1][2];
        int v = towns[i][2];
        int w = towns[i][1] - towns[i-1][1];
        edges[edge_count++] = {u, v, w};
    }
    // Kruskal's algorithm
    sort(edges, edges + edge_count);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    long long total_cost = 0;
    int connected = 0;
    for (int i = 0; i < edge_count && connected < n - 1; ++i) {
        int u_root = find_root(edges[i].u);
        int v_root = find_root(edges[i].v);
        if (u_root != v_root) {
            parent[u_root] = v_root;
            total_cost = (total_cost + edges[i].weight) % MOD;
            ++connected;
        }
    }
    cout << total_cost << endl;
    return 0;
}