Bài A: Chuyển đổi chuỗi

Cho chuỗi độ dài n và hai ký tự char1, char2. Thay thế tất cả ký tự không phải char1 trong chuỗi bằng char2.

Phương pháp

Mô phỏng trực tiếp qua vòng lặp trên từng ký tự.

Mã nguồn

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

int main() {
    int length;
    char target_char, replacement;
    string input;
    
    cin >> length >> target_char >> replacement >> input;
    
    for (int idx = 0; idx < input.size(); idx++) {
        if (input[idx] != target_char) {
            input[idx] = replacement;
        }
    }
    
    cout << input << endl;
    return 0;
}

Bài B: Phân khu điểm

Có n trận thi với điểm khởi đầu initial_rating. Mỗi trận có thuộc tính division và thay đổi điểm score_delta. Điểm chỉ thay đổi nếu thuộc phân khu tương ứng (phân khu 1: [1600, 2799], phân khu 2: [1200, 2399]). Tính điểm cuối cùng.

Phương pháp

Mô phỏng từng trận thi theo điều kiện phân khu.

Mã nguồn

#include <iostream>
using namespace std;

int main() {
    int match_count, current_rating;
    cin >> match_count >> current_rating;
    
    for (int i = 0; i < match_count; i++) {
        int division_type, score_change;
        cin >> division_type >> score_change;
        
        if ((division_type == 1 && current_rating >= 1600 && current_rating <= 2799) ||
            (division_type == 2 && current_rating >= 1200 && current_rating <= 2399)) {
            current_rating += score_change;
        }
    }
    
    cout << current_rating << endl;
    return 0;
}

Bài C: Thứ tự hoàn hảo

Có 5 bài toán A-E với điểm số tương ứng. Liệt kê 31 trường hợp kết hợp bài thi theo thứ tự điểm cao nhất, và nếu điểm bằng nhau thì theo thứ tự từ điển của tên bài.

Phương pháp

Tạo tất cả tổ hợp (dùng bitmask), tính điểm cho từng tổ hợp, sắp xếp theo điểm giảm dần và tên bài tăng dần.

Mã nguồn

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

int main() {
    vector<int> problem_scores(5);
    for (int i = 0; i < 5; i++) {
        cin >> problem_scores[i];
    }
    
    string problem_names = "ABCDE";
    vector<pair<int, string>> combinations;
    
    for (int mask = 1; mask < (1 << 5); mask++) {
        int total_score = 0;
        string selected = "";
        for (int j = 0; j < 5; j++) {
            if (mask & (1 << j)) {
                selected += problem_names[j];
                total_score += problem_scores[j];
            }
        }
        combinations.push_back({total_score, selected});
    }
    
    sort(combinations.begin(), combinations.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    
    for (auto& combo : combinations) {
        cout << combo.second << endl;
    }
    return 0;
}

Bài D: Dãy tuần hoàn

Cho dãy vô hạn tuần hoàn với chu kỳ n. Kiểm tra xem tồn tại dãy con liên tiếp có tổng bằng s không.

Phương pháp

Sử dụng tổng tiền tố và tập hợp để kiểm tra hiệu hai tổng tiền tố. Xử lý chu kỳ bằng cách tính tổng tiền tố cho 2 chu kỳ.

Mã nguồn

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

int main() {
    int cycle_length, target_sum;
    cin >> cycle_length >> target_sum;
    
    vector<int> values(cycle_length);
    for (int i = 0; i < cycle_length; i++) {
        cin >> values[i];
    }
    
    vector<int> prefix(2 * cycle_length + 1, 0);
    for (int i = 1; i <= cycle_length; i++) {
        prefix[i] = prefix[i-1] + values[i-1];
    }
    for (int i = cycle_length + 1; i <= 2 * cycle_length; i++) {
        prefix[i] = prefix[i-1] + values[i - cycle_length - 1];
    }
    
    int cycle_total = prefix[cycle_length];
    target_sum %= cycle_total;
    if (target_sum == 0) {
        cout << "Yes" << endl;
        return 0;
    }
    
    set<int> seen;
    seen.insert(0);
    for (int i = 1; i <= 2 * cycle_length; i++) {
        if (seen.find(prefix[i] - target_sum) != seen.end()) {
            cout << "Yes" << endl;
            return 0;
        }
        seen.insert(prefix[i]);
    }
    
    cout << "No" << endl;
    return 0;
}

Bài E: Dạng súc nhầy

Trên lưới h x w có các khối súc nhầy với cường độ strength[i][j]. Khối ban đầu tại (a,b) sẽ hấp thụ các khối lân cận có cường độ nhỏ hơn. Tính cường độ cuối cùng.

Phương pháp

BFS với hàng đợi ưu tiên (min-heap) để luôn chọn khối nhỏ nhất hấp thụ trước.

Mã nguồn

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

typedef pair<int, int> pii;
const int MAX = 505;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

struct Cell {
    int x, y, strength;
    bool operator < (const Cell& other) const {
        return strength > other.strength;
    }
};

int main() {
    int height, width, start_x, start_y;
    long long multiplier;
    cin >> height >> width >> multiplier >> start_x >> start_y;
    
    vector<vector<int>> grid(height + 1, vector<int>(width + 1));
    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            cin >> grid[i][j];
        }
    }
    
    vector<vector<bool>> visited(height + 1, vector<bool>(width + 1, false));
    priority_queue<Cell> pq;
    pq.push({start_x, start_y, grid[start_x][start_y]});
    visited[start_x][start_y] = true;
    long long total_strength = 0;
    
    while (!pq.empty()) {
        Cell current = pq.top();
        pq.pop();
        
        if (total_strength * multiplier >= current.strength) {
            break;
        }
        
        total_strength += current.strength;
        
        for (int d = 0; d < 4; d++) {
            int nx = current.x + dx[d];
            int ny = current.y + dy[d];
            if (nx >= 1 && nx <= height && ny >= 1 && ny <= width && !visited[nx][ny]) {
                visited[nx][ny] = true;
                pq.push({nx, ny, grid[nx][ny]});
            }
        }
    }
    
    cout << total_strength << endl;
    return 0;
}