Hướng dẫn cho SWORD (OLP MT&TN 2023 Sơ Loại Không Chuyên)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Flower_On_Stone

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).

Tutorial

Với \(n\) rất nhỏ, ta có thể duyệt vét cạn tất cả các thứ tự tiêu diệt các boss và chọn ra thứ tự giết được nhiều nhất.

Độ phức tạp: \(\mathcal{O}(n!)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

int numBoss, S;
int power[MAX_N], bonus[MAX_N], id[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> numBoss >> S;
    for (int index = 1; index <= numBoss; index++) {
        cin >> power[index] >> bonus[index];
    }

    for (int index = 1; index <= numBoss; index++) {
        id[index] = index;
    }

    int answer = 0;
    do {
        int cnt = 0;
        long long sum = S;
        for (int index = 1; index <= numBoss; index++) {
            if (sum <= power[id[index]]) {
                break;
            }
            cnt++;
            sum += bonus[id[index]];
        }
        answer = max(answer, cnt);
    } while (next_permutation(id + 1, id + numBoss + 1));

    cout << answer;

    return 0;
}

Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{3}\).

Tutorial

Với \(n \leq 1000\), ta có một thuật toán tham lam như sau: Ta sẽ xem thử trong danh sách các con boss chưa bị tiêu diệt, ta tiêu diệt một con boss bất kỳ mà ta có thể tiêu diệt và tăng điểm sức mạnh của bản thân. Lặp lại điều trên cho tới khi không tiêu diệt được thêm con boss nào nữa.

Độ phức tạp: \(\mathcal{O}(n^{2})\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

int numBoss;
long long S;
int power[MAX_N], bonus[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> numBoss >> S;
    for (long long index = 1; index <= numBoss; index++) {
        cin >> power[index] >> bonus[index];
    }

    long long answer = 0;
    while (true) {
        bool found = false;
        for (long long index = 1; index <= numBoss; index++) {
            if (power[index] != -1 && power[index] < S) {
                found = true;
                S += bonus[index];
                power[index] = -1;
                answer++;
                break;
            }
        }
        if (!found) {
            break;
        }
    }

    cout << answer;

    return 0;
}

Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Với \(n\) lớn, ta cần một thuật toán hiệu quả hơn. Ta nhận xét từ thuật toán ở subtask 2 rằng nếu ta không thể tiêu diệt được con boss có sức mạnh nhỏ nhất hiện tại thì ta chắc chắn không thể tiêu diệt thêm bất kỳ con boss nào khác. Do đó, ta suy ra được phương án tối ưu đó chính là tiêu diệt các con boss theo thứ tự tăng dần theo sức mạnh.

Độ phức tạp: \(\mathcal{O}(n \times log_{2}(n))\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

int numBoss;
long long S;
pair<int, int> boss[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> numBoss >> S;
    for (int index = 1; index <= numBoss; index++) {
        cin >> boss[index].first >> boss[index].second;
    }

    sort(boss + 1, boss + numBoss + 1);
    for (int index = 1; index <= numBoss; index++) {
        if (S <= boss[index].first) {
            cout << index - 1;
            return 0;
        }
        S += boss[index].second;
    }

    cout << numBoss;

    return 0;
}

Bình luận

Không có bình luận nào.