Hướng dẫn giải

Bát Giới có $n$ berllar, hộp giấy giá $a$ (1 lít), chai thủy tinh giá $b$ (1 lít) và cửa hàng trả lại $c$ khi trả chai rỗng ($c < b$). Mỗi lít sữa chai thực chất tốn $d = b - c$ nếu mua rồi trả lại chai, nhưng cần có đủ $b$ tiền tại thời điểm mua chai. Hộp giấy không được hoàn trả nên luôn tốn đúng $a$.

Ý tưởng chính: mua các chai trước (vì tiền luôn giảm ít hơn khi trả chai), sau đó dùng số tiền còn lại mua hộp giấy.

Sub 1: Vét cạn — ~O(k_{max})~, dùng khi ~k_{max} \le 10^6~

Với $k$ lần mua-trả chai, số tiền còn lại là $n - k \cdot d$ và mua được thêm $\lfloor (n - kd)/a \rfloor$ hộp giấy. Tổng số lít là $k + \lfloor (n - kd)/a \rfloor$. Thử mọi $k$ từ $0$ đến $k_{max}$ và lấy giá trị lớn nhất.

Số lần tối đa $k{max}$: lần mua thứ $k$ cần tiền hiện có $\ge b$, tức $n - (k-1)d \ge b$, nên $k{max} = \lfloor (n-b)/d \rfloor + 1$ nếu $n \ge b$, ngược lại $k_{max} = 0$.

Kết quả chạy riêng sub này: đúng 56/83 test (các test sai/quá giờ còn lại đều có $k_{max} > 10^6$, nằm ngoài miền của sub này).

Sub 2: Công thức — ~O(1)~

Hàm $f(k) = k + \lfloor (n - kd)/a \rfloor$ chỉ có hai khả năng tốt nhất:

• Nếu $d < a$: mỗi lần mua-trả chai làm tăng $f$ hoặc giữ nguyên, nên $k = k_{max}$.
• Nếu $d \ge a$: mỗi lần tăng $k$ làm $f$ không tăng, nên $k = 0$.

Đáp án là $k + \lfloor (n - kd)/a \rfloor$ với $k$ chọn như trên.

Bẫy cần chú ý: $n$, $a$, $b$ có thể đến $10^{18}$ nên dùng long long. Các tích $k \cdot d$ không vượt quá $n$ nên không tràn.

Chương trình hoàn chỉnh

Chương trình đọc $n, a, b, c$, tính $k{max}$. Nếu $k{max} \le 10^6$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi, sub1 vẫn ăn điểm các test nhỏ nếu chưa làm được công thức.

#include <bits/stdc++.h>
using namespace std;

long long n, a, b, c;
long long kmax;      // số lần mua-trả chai tối đa
// Gọi d = b - c: chi phí thực tế của một lít sữa chai (mua b, trả lại chai được c)

// Sub 1: vét cạn — thử mọi số lần k mua sữa chai rồi trả lại (k từ 0 đến kmax),
// với mỗi k, số tiền còn lại mua được (n - k*(b-c)) / a hộp giấy.
// Dùng khi kmax <= 10^6
void sub1() {
    long long best = 0;
    long long d = b - c;
    for (long long k = 0; k <= kmax; k++) {
        long long money = n - k * d;          // tiền còn lại sau k lần mua-trả chai
        long long val = k + money / a;        // k lít chai + số hộp giấy mua được
        best = max(best, val);
    }
    cout << best << "\n";
}

// Sub 2: công thức — xét hai khả năng: không mua chai (k = 0), hoặc mua chai tối đa (k = kmax).
// Nếu b - c < a thì mỗi lít chai rẻ hơn hộp giấy nên mua chai tối đa; ngược lại không mua chai.
void sub2() {
    long long d = b - c;
    long long k = (d < a) ? kmax : 0;
    cout << k + (n - k * d) / a << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> a >> b >> c;
    long long d = b - c;
    // Số lần mua chai tối đa: lần mua thứ k cần tiền hiện có >= b,
    // tức n - (k-1)*d >= b  =>  k <= (n - b) / d + 1
    kmax = (n >= b) ? (n - b) / d + 1 : 0;
    if (kmax <= 1000000) sub1();   // ít lần mua chai: vét cạn cho chắc
    else sub2();                   // nhiều lần: công thức O(1)
    return 0;
}