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

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: kitsune

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

Tutorial

Ta lần lượt đi qua các trường hợp sau:

Mua được quả ở cả cửa hàng \(1\) và \(2\).
Chỉ mua được quả ở cửa hàng \(1\).
Chỉ mua được quả ở của hàng \(2\).

Khi xét đén một trường hợp, ta sẽ tính toán xem nó sẽ xảy ra bao nhiêu lần trước khi xét đến trường hợp tiếp theo. Số lần xảy ra của một trường hợp là \(\dfrac{\text{số tiền còn lại}}{\text{tổng số tiền mua quả}}\).

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

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

int n;
long long m;
int a[MAX_N];

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    long long answer = 2 * (m / (a[1] + a[2]));
    m %= (a[1] + a[2]);

    answer += m / a[1];
    m %= a[1];

    answer += m / a[2];
    m %= a[2];

    cout << answer << "\n";

    return 0;
}

Subtask \(2\) (\(30\%\) số điểm): \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\).

Subtask \(3\) (\(30\%\) số điểm): \(m \leq \min(a_{1}, a_{2}, \ldots, a_{n}) \times 10^{6}\).

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

Tutorial

Lấy ý tưởng từ subtask 1, ta duyệt qua các gian hàng và tính tổng số tiền của những quả mua được rồi tính số lần trường hợp này xảy ra. Ta sẽ lặp lại cho đến khi không còn mua được quả nào nữa.

Vì sau khi xét xong một trường hợp, số tiền giảm đi ít nhất là một nữa nên số lần duyệt sẽ không quá \(\log m\) lần.

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

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

int n;
long long m;
int a[MAX_N];

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

    cin >> n >> m;

    for (int index = 1; index <= n; index++) {
        cin >> a[index];
    }

    long long answer = 0;
    while (true) {
        int cnt = 0;
        long long sum = 0;
        for (int index = 1; index <= n; index++) {
            if (m >= a[index]) {
                cnt++;
                sum += a[index];
                m -= a[index];
            }
        }

        if (cnt == 0) {
            break;
        }

        answer += cnt * (1 + m / sum);
        m %= sum;
    }

    cout << answer << "\n";

    return 0;
}

Bình luận

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