A - Antenna Analysis

The mathematical expression can be decomposed into two separate components:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, c;
    cin >> n >> c;
    
    priority_queue<long long=""> part1, part2;
    long long result = 0;
    
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        
        long long value1 = c * i - x;
        long long value2 = c * i + x;
        
        part1.push(value1);
        part2.push(value2);
        
        if (i > 1) {
            long long current = max(part1.top() + x - c * i, part2.top() - x - c * i);
            cout << current << (i == n ? '\n' : ' ');
        } else {
            cout << "0" << (i == n ? '\n' : ' ');
        }
    }
    
    return 0;
}
</long></vector></queue></iostream>

C - Customs Controls

The solution involves coloring nodes to block paths. We start by coloring the start node and its connected edges with one color, then proceed to block remaining paths by coloring appropriately. The special case when n=2 and k=1 is impossible.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector>> graph(n + 1);
    vector<long long=""> costs(n + 1);
    vector<long long=""> dist(n + 1, LLONG_MAX / 2);
    
    for (int i = 1; i <= n; ++i) {
        cin >> costs[i];
    }
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    if (n == 2 && k == 1) {
        cout << "impossible\n";
        return 0;
    }
    
    dist[1] = costs[1];
    priority_queue<pair int="" long="">, vector<pair int="" long="">>, greater<pair int="" long="">>> pq;
    pq.push({dist[1], 1});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d != dist[u]) continue;
        
        for (int v : graph[u]) {
            if (dist[v] > d + costs[v]) {
                dist[v] = d + costs[v];
                pq.push({dist[v], v});
            }
        }
    }
    
    vector<vector>> forwardEdges(n + 1);
    vector<vector>> backwardEdges(n + 1);
    vector<bool> visited(n + 1, false);
    queue<int> q;
    
    q.push(n);
    visited[n] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : graph[u]) {
            if (dist[v] + costs[u] == dist[u]) {
                forwardEdges[u].push_back(v);
                forwardEdges[v].push_back(u);
                backwardEdges[v].push_back(u);
                
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
    }
    
    vector<char> assignment(n + 1, '.');
    int north = k, south = n - k;
    
    auto assignColors = [&]() {
        for (int i = 1; i <= n; ++i) {
            if (assignment[i] == '.') {
                if (north > 0) {
                    north--;
                    assignment[i] = 'N';
                } else {
                    south--;
                    assignment[i] = 'S';
                }
            }
            cout << assignment[i];
        }
        cout << '\n';
    };
    
    int edgeCount = 0;
    for (int i = 1; i <= n; ++i) {
        if (!forwardEdges[i].empty()) edgeCount++;
    }
    
    if (k > n - k) {
        int startEdges = forwardEdges[1].size();
        int endEdges = forwardEdges[n].size();
        
        if (startEdges + 1 <= k) {
            assignment[1] = 'N';
            visited.assign(n + 1, false);
            queue<int> colorQ;
            colorQ.push(1);
            visited[1] = true;
            
            while (!colorQ.empty()) {
                int u = colorQ.front();
                colorQ.pop();
                
                for (int v : forwardEdges[u]) {
                    if (!visited[v]) {
                        assignment[v] = 'N';
                        visited[v] = true;
                        colorQ.push(v);
                    }
                }
            }
            assignColors();
            return 0;
        }
        
        if (endEdges + 1 <= k) {
            assignment[n] = 'N';
            visited.assign(n + 1, false);
            queue<int> colorQ;
            colorQ.push(n);
            visited[n] = true;
            
            while (!colorQ.empty()) {
                int u = colorQ.front();
                colorQ.pop();
                
                for (int v : forwardEdges[u]) {
                    if (!visited[v]) {
                        assignment[v] = 'N';
                        visited[v] = true;
                        colorQ.push(v);
                    }
                }
            }
            assignColors();
            return 0;
        }
    } else {
        int startEdges = forwardEdges[1].size();
        int endEdges = forwardEdges[n].size();
        
        if (startEdges + 1 <= n - k) {
            assignment[1] = 'S';
            visited.assign(n + 1, false);
            queue<int> colorQ;
            colorQ.push(1);
            visited[1] = true;
            
            while (!colorQ.empty()) {
                int u = colorQ.front();
                colorQ.pop();
                
                for (int v : forwardEdges[u]) {
                    if (!visited[v]) {
                        assignment[v] = 'S';
                        visited[v] = true;
                        colorQ.push(v);
                    }
                }
            }
            assignColors();
            return 0;
        }
        
        if (endEdges + 1 <= n - k) {
            assignment[n] = 'S';
            visited.assign(n + 1, false);
            queue<int> colorQ;
            colorQ.push(n);
            visited[n] = true;
            
            while (!colorQ.empty()) {
                int u = colorQ.front();
                colorQ.pop();
                
                for (int v : forwardEdges[u]) {
                    if (!visited[v]) {
                        assignment[v] = 'S';
                        visited[v] = true;
                        colorQ.push(v);
                    }
                }
            }
            assignColors();
            return 0;
        }
    }
    
    if (k > 0) {
        assignment[1] = 'N';
        k--;
    }
    
    for (int v : forwardEdges[1]) {
        if (k > 0) {
            assignment[v] = 'N';
            k--;
        } else {
            assignment[v] = 'S';
        }
    }
    
    assignColors();
    return 0;
}
</int></int></int></int></char></int></bool></vector></vector></pair></pair></pair></long></long></vector></climits></queue></vector></iostream>

D - Deceptive Directions

The tresaure must be located at a distance equal to the instruction length from the starting point. Since each step provides incorrect directions, we explore all three alternative directions at each step using BFS and check if the final distance matches the instruction length.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m, n;
    cin >> m >> n;
    
    vector<vector>> grid(n, vector<char>(m));
    vector<vector>> dist(n, vector<int>(m, INT_MAX));
    vector<vector>> pathDist(n, vector<int>(m, INT_MAX));
    vector<vector>> visited(n, vector<bool>(m, false));
    
    int startX, startY;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') {
                startX = i;
                startY = j;
            }
        }
    }
    
    string instructions;
    cin >> instructions;
    
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    dist[startX][startY] = 0;
    queue<pair int="">> q;
    q.push({startX, startY});
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            
            if (dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    pathDist[startX][startY] = 0;
    q.push({startX, startY});
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        visited[x][y] = true;
        
        int step = pathDist[x][y];
        
        if (step >= instructions.size()) continue;
        
        int forbiddenDir;
        if (instructions[step] == 'N') forbiddenDir = 0;
        else if (instructions[step] == 'S') forbiddenDir = 1;
        else if (instructions[step] == 'W') forbiddenDir = 2;
        else forbiddenDir = 3;
        
        for (int i = 0; i < 4; ++i) {
            if (i == forbiddenDir) continue;
            
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (visited[nx][ny]) continue;
            
            if (pathDist[x][y] + 1 == dist[nx][ny]) {
                pathDist[nx][ny] = dist[nx][ny];
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (pathDist[i][j] == instructions.size()) {
                grid[i][j] = '!';
            }
        }
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << grid[i][j];
        }
        cout << '\n';
    }
    
    return 0;
}
</pair></bool></vector></int></vector></int></vector></char></vector></climits></string></queue></vector></iostream>

G - Grazed Grains

The problem requires calculating the union area of multiple circles. Two approaches are viable: calculating circle intersections or using adaptive Simpson integration.

Approach 1: Circle Intersection Method

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

const double EPS = 1e-8;
const double PI = acos(-1.0);

struct Circle {
    double x, y, r;
};

struct Point {
    double x, y;
};

double distance(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int circleIntersection(Circle c1, Circle c2, Point &p1, Point &p2) {
    double d = distance({c1.x, c1.y}, {c2.x, c2.y});
    
    if (d > c1.r + c2.r + EPS) return 0;
    if (d < fabs(c1.r - c2.r) - EPS) return 0;
    
    double a = (c1.r * c1.r - c2.r * c2.r + d * d) / (2 * d);
    double h = sqrt(c1.r * c1.r - a * a);
    
    Point mid = {
        c1.x + a * (c2.x - c1.x) / d,
        c1.y + a * (c2.y - c1.y) / d
    };
    
    p1.x = mid.x + h * (c2.y - c1.y) / d;
    p1.y = mid.y - h * (c2.x - c1.x) / d;
    p2.x = mid.x - h * (c2.y - c1.y) / d;
    p2.y = mid.y + h * (c2.x - c1.x) / d;
    
    if (fabs(d - c1.r - c2.r) < EPS || fabs(d - fabs(c1.r - c2.r)) < EPS) return 1;
    return 2;
}

double sectorArea(double r, double angle) {
    return 0.5 * r * r * angle;
}

double triangleArea(Point a, Point b, Point c) {
    return fabs(cross(a, b, c)) / 2.0;
}

double segmentArea(double r, double angle) {
    return sectorArea(r, angle) - triangleArea({0, 0}, {r, 0}, {r * cos(angle), r * sin(angle)});
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<circle> circles(n);
    for (int i = 0; i < n; ++i) {
        cin >> circles[i].x >> circles[i].y >> circles[i].r;
    }
    
    double totalArea = 0.0;
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            Point p1, p2;
            int intersections = circleIntersection(circles[i], circles[j], p1, p2);
            
            if (intersections == 0) continue;
            
            double angle1 = atan2(p1.y - circles[i].y, p1.x - circles[i].x);
            double angle2 = atan2(p2.y - circles[i].y, p2.x - circles[i].x);
            
            double sector1 = sectorArea(circles[i].r, fabs(angle2 - angle1));
            double triangle1 = triangleArea({circles[i].x, circles[i].y}, p1, p2);
            
            totalArea += sector1 - triangle1;
        }
    }
    
    cout << fixed << setprecision(10) << totalArea << '\n';
    
    return 0;
}
</circle></cmath></algorithm></vector></iostream>

Approach 2: Adaptive Simpson Integration

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

const double EPS = 1e-8;
const double PI = acos(-1.0);

struct Circle {
    long long x, y;
    long long r;
};

struct Segment {
    double l, r;
};

bool operator<(const Segment &a, const Segment &b) {
    if (fabs(a.l - b.l) < EPS) return a.r < b.r;
    return a.l < b.l;
}

struct Point {
    long long x, y;
};

double distance(Point a, Point b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}

double f(double x, const vector<circle> &circles) {
    vector<segment> segments;
    
    for (const auto &circle : circles) {
        if (x > circle.x + circle.r || x < circle.x - circle.r) continue;
        
        double dx = x - circle.x;
        double dy = sqrt(1.0 * circle.r * circle.r - dx * dx);
        
        segments.push_back({circle.y - dy, circle.y + dy});
    }
    
    if (segments.empty()) return 0.0;
    
    sort(segments.begin(), segments.end());
    
    double total = 0.0;
    double current = segments[0].l;
    
    for (const auto &seg : segments) {
        if (seg.r > current) {
            total += seg.r - max(current, seg.l);
            current = seg.r;
        }
    }
    
    return total;
}

double simpson(double l, double r, double fl, double fr, double fm) {
    return (r - l) * (fl + 4.0 * fm + fr) / 6.0;
}

double adaptiveSimpson(double l, double r, double fl, double fr, double fm, double whole) {
    double mid = (l + r) / 2.0;
    double flm = f(l, mid);
    double frm = f(mid, r);
    double left = simpson(l, mid, fl, fm, flm);
    double right = simpson(mid, r, fm, fr, frm);
    
    if (fabs(left + right - whole) < EPS) return whole;
    
    return adaptiveSimpson(l, mid, fl, fm, flm, left) + adaptiveSimpson(mid, r, fm, fr, frm, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<circle> circles(n);
    for (int i = 0; i < n; ++i) {
        cin >> circles[i].x >> circles[i].y >> circles[i].r;
    }
    
    sort(circles.begin(), circles.end(), [](const Circle &a, const Circle &b) {
        return a.r < b.r;
    });
    
    double totalArea = 0.0;
    double left = circles[0].x - circles[0].r;
    double right = circles[0].x + circles[0].r;
    
    for (int i = 1; i < n; ++i) {
        right = max(right, 1.0 * circles[i].x + circles[i].r);
    }
    
    double mid = (left + right) / 2.0;
    double fl = f(left, circles);
    double fr = f(right, circles);
    double fm = f(mid, circles);
    
    totalArea = adaptiveSimpson(left, right, fl, fr, fm, simpson(left, right, fl, fr, fm));
    
    cout << fixed << setprecision(3) << totalArea << '\n';
    
    return 0;
}
</circle></segment></circle></cmath></algorithm></vector></iostream>

J - Joint Jog Jam

This problem involves calculating the maximum distance between two moving points following specific paths.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long x[5], y[5];
    for (int i = 1; i <= 4; ++i) {
        cin >> x[i] >> y[i];
    }
    
    long long a, b, c;
    c = (x[1] - x[2]) * (x[1] - x[2]) + (y[1] - y[2]) * (y[1] - y[2]);
    b = 2 * ((x[1] - x[2]) * (x[2] + x[3] - x[1] - x[4]) + (y[1] - y[2]) * (y[2] + y[3] - y[1] - y[4]));
    a = (x[2] + x[3] - x[1] - x[4]) * (x[2] + x[3] - x[1] - x[4]) + 
        (y[2] + y[3] - y[1] - y[4]) * (y[2] + y[3] - y[1] - y[4]);
    
    double maxDist = 0.0;
    if (a != 0) {
        maxDist = (4.0 * a * c - b * b) / (4.0 * a);
    }
    
    maxDist = max(maxDist, 1.0 * (x[1] - x[2]) * (x[1] - x[2]) + (y[1] - y[2]) * (y[1] - y[2]));
    maxDist = max(maxDist, 1.0 * (x[3] - x[4]) * (x[3] - x[4]) + (y[3] - y[4]) * (y[3] - y[4]));
    
    cout << fixed << setprecision(10) << sqrt(maxDist) << '\n';
    
    return 0;
}
</cmath></iostream>

K - Knot Knowledge

The solution involves sorting two sequences and finding the first mismatched element, or returning the last element if all match.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<long long=""> sequence1(n);
    vector<long long=""> sequence2(n - 1);
    
    for (int i = 0; i < n; ++i) {
        cin >> sequence1[i];
    }
    
    for (int i = 0; i < n - 1; ++i) {
        cin >> sequence2[i];
    }
    
    sort(sequence1.begin(), sequence1.end());
    sort(sequence2.begin(), sequence2.end());
    
    for (int i = 0; i < n - 1; ++i) {
        if (sequence1[i] != sequence2[i]) {
            cout << sequence1[i] << '\n';
            return 0;
        }
    }
    
    cout << sequence1[n - 1] << '\n';
    return 0;
}
</long></long></algorithm></vector></iostream>

L - Locust Locus

The problem requires finding the earliest year when both locust species appear together, which is determined by the least common multiple of their cycles.

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

long long gcd(long long a, long long b) {
    while (b) {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    long long earliestYear = LLONG_MAX;
    
    for (int i = 0; i < n; ++i) {
        long long year, cycle1, cycle2;
        cin >> year >> cycle1 >> cycle2;
        
        earliestYear = min(earliestYear, year + lcm(cycle1, cycle2));
    }
    
    cout << earliestYear << '\n';
    return 0;
}
</numeric></vector></iostream>