Editorial for FRUITMARKET (OLP MT&TN 2023 Sơ Loại Chuyên Tin)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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;
}

Comments

There are no comments at the moment.