Problem T1

Problem Statement Given n team members with their individual speeds a[i] and carrying capacities w[i], determine the maximum achievable team speed where faster members can assist slower ones.

Solution Approach The key insight is that the answer exhibits monotonicity, making binary search applicable. If a target speed x can be achieved, then any speed lower than x is also achievable. Conversely, if x cannot be reached, no higher speed is possible.

To verify whether speed x is achievable, partition all members into two categories:

Carriers: members with speed ≥ x who can carry others Passengers: members with speed < x who require assistance

The verification succeeds when all passengers find carriers. A greedy strategy works optimally: assign the strongest carriers to the most demanding passengers. This can be efficiently implemented using priority queues to match carriers and passengers.

Time Complexity: O(n log(V_max)) where V_max represents the maximum speed value.

Implementation

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int speed[MAXN], carry[MAXN], N;
priority_queue<int> carriers, passengers;

bool canAchieve(int targetSpeed) {
    carriers = priority_queue<int>();
    passengers = priority_queue<int>();
    
    for (int i = 0; i < N; i++) {
        if (speed[i] >= targetSpeed) {
            carriers.push(speed[i] + carry[i] - targetSpeed);
        } else {
            passengers.push(carry[i]);
        }
    }
    
    while (!passengers.empty()) {
        if (carriers.empty()) return false;
        if (carriers.top() < passengers.top()) return false;
        carriers.pop();
        passengers.pop();
    }
    return true;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        int high = 0;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &speed[i], &carry[i]);
            high = max(high, speed[i]);
        }
        
        int result = 0, low = 0, highBound = high;
        while (low <= highBound) {
            int mid = (low + highBound) >> 1;
            if (canAchieve(mid)) {
                result = mid;
                low = mid + 1;
            } else {
                highBound = mid - 1;
            }
        }
        printf("%d\n", result);
    }
    return 0;
}

Problem T2

Problem Statement Construct a sequence of rectangles covering a grid of size n×n, where one black cell is given at position (bx, by). Each rectangle must be placed within grid boundaries.

Solution Approach This is a constructive geometry problem. Starting from the black cell, expand outward by creating squares in an alternating L-shape pattern (two L-shapes forming a square). Continue expansion until reaching any grid boundary.

A crucial property ensures constructbiility: the sum of distances from the current square to two perpendicular boundaries always equals the distance to the parallel boundary. This invariant guarantees a valid solution exists.

The algorithm systematically expands the bounding box in four directions, outputting rectangles when the expansion reaches a bonudary.

Time Complexity: O(n)

Implementation

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

struct Rectangle {
    int row, col, height, width;
    void output() {
        printf("%d %d %d %d\n", row, col, height, width);
    }
};

int main() {
    int n, startRow, startCol;
    scanf("%d %d %d", &n, &startRow, &startCol);
    
    int top = startRow, bottom = startRow;
    int left = startCol, right = startCol;
    vector<Rectangle> result;
    
    printf("Yes\n%d\n", n - 1);
    for (int step = 1; step < n; step++) {
        if (top > 1 && left > 1) {
            top--;
            left--;
            result.push_back({top, left, bottom - top, right - left});
        } else if (top > 1 && right < n) {
            top--;
            right++;
            result.push_back({top, right, bottom - top, left - right});
        } else if (bottom < n && left > 1) {
            bottom++;
            left--;
            result.push_back({bottom, left, top - bottom, right - left});
        } else {
            bottom++;
            right++;
            result.push_back({bottom, right, top - bottom, left - right});
        }
    }
    
    for (const auto& rect : result) {
        rect.output();
    }
    return 0;
}