Bài A: Di chuyển theo hướng

Do giới hạn nhỏ, ta có thể mô phỏng toàn bộ quá trình di chuyển bằng cách lặp lại chuỗi lệnh nhiều lần. Chỉ cần kiểm tra sau mỗi bước xem đã đến tọa độ mục tiêu chưa.

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

void process() {
    int n, tx, ty;
    string moves;
    cin >> n >> tx >> ty >> moves;

    int cx = 0, cy = 0;
    for (int rep = 0; rep < 50; ++rep) {
        for (char dir : moves) {
            if (dir == 'N') cy++;
            else if (dir == 'S') cy--;
            else if (dir == 'E') cx++;
            else cx--;

            if (cx == tx && cy == ty) {
                cout << "Yes\n";
                return;
            }
        }
    }
    cout << "No\n";
}

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

Bài B: Tối ưu hóa phép biến đổi

Bài toán yêu cầu tính chi phí tối thiểu để biến đổi dãy số sao cho tất cả phần tử nằm trong đoạn [0, n-1]. Cần xét các trường hợp đặc biệt khi b = 0 và xử lý riêng giá trị c:

• Nếu c < n-2 → không thể đạt được → trả về -1.
• Nếu c nằm trong [n-2, n-1] → chi phí là n-1.
• Nếu c ≥ n → chi phí là n.
• Nếu b > 0 → đếm số phần tử vượt quá n-1.

#include <iostream>
using namespace std;
typedef long long ll;

void handleCase() {
    ll len, step, val;
    cin >> len >> step >> val;

    if (step == 0) {
        if (val < len - 2) {
            cout << "-1\n";
        } else {
            cout << (val <= len - 1 ? len - 1 : len) << '\n';
        }
        return;
    }

    if (val >= len) {
        cout << len << '\n';
        return;
    }

    ll remain = max(0LL, len - 1 - val) / step + 1;
    cout << len - remain << '\n';
}

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

Bài C: Chia bánh tối ưu

Sử dụng kỹ thuật tiền tố và ánh xạ để tìm đoạn con có tổng lớn nhất sau khi chia bánh thành đúng m+1 phần. Duyệt từ đầu để ghi nhận số lượng phần tối đa có thể cắt, sau đó duyệt ngược để kết hợp với dữ liệu đã lưu.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;

const int MAXN = 200005;
ll prefix[MAXN], leftParts[MAXN], rightParts[MAXN];
int startPos[MAXN];

void solveCake() {
    int pieces, cuts;
    ll minSize;
    cin >> pieces >> cuts >> minSize;

    for (int i = 1; i <= pieces; ++i) {
        cin >> prefix[i];
        prefix[i] += prefix[i - 1];
    }

    map firstOccur;
    firstOccur[0] = 0;
    ll current = 0;

    for (int i = 1; i <= pieces; ++i) {
        leftParts[i] = leftParts[i - 1];
        if (current < minSize) current += prefix[i] - prefix[i - 1];
        if (current >= minSize) {
            current = 0;
            leftParts[i]++;
        }
        if (!firstOccur.count(leftParts[i])) 
            firstOccur[leftParts[i]] = i;
    }

    if (leftParts[pieces] < cuts) {
        cout << "-1\n";
        return;
    }

    current = 0;
    rightParts[pieces + 1] = 0;
    ll best = prefix[pieces] - prefix[firstOccur[cuts]];

    for (int i = pieces; i >= 1; --i) {
        rightParts[i] = rightParts[i + 1];
        if (current < minSize) current += prefix[i] - prefix[i - 1];
        if (current >= minSize) {
            current = 0;
            rightParts[i]++;
        }
        if (firstOccur.count(cuts - rightParts[i])) {
            int splitPoint = firstOccur[cuts - rightParts[i]];
            best = max(best, prefix[i - 1] - prefix[splitPoint]);
        }
    }

    cout << best << '\n';
}

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