Two Cinemas#13120

Two Cinemas (Editorial)

Solution

Since a\le b, before multiplying the money, it is sufficient to buy tickets only to the first cinema, as tickets to the second cinema are no cheaper.

Suppose we buy tickets to the first cinema before multiplying the money. After the multiplication, we will have (n-qa)x hryvnias left, so the total number of tickets will be

f(q)=q+\left\lfloor\frac{(n-qa)x}{b}\right\rfloor, \qquad 0\le q\le\left\lfloor\frac{n}{a}\right\rfloor.

If ax\ge b, then q\le qax/b, hence

f(q)\le\left\lfloor\frac{qax}{b}+\frac{(n-qa)x}{b}\right\rfloor =\left\lfloor\frac{nx}{b}\right\rfloor.

This value can be achieved by immediately multiplying all the money by and buying tickets to the second cinema.

Otherwise, if ax\le b, then x/b\le1/a, so

f(q)\le q+\left\lfloor\frac{n-qa}{a}\right\rfloor =\left\lfloor\frac{n}{a}\right\rfloor.

This value can be achieved by buying tickets only to the first cinema without multiplying the money.

Therefore, regardless of the relationship between and , the answer is

\boxed{\max\left(\left\lfloor\frac{n}{a}\right\rfloor, \left\lfloor\frac{nx}{b}\right\rfloor\right)}.

The product can be as large as 10^{18}, so we use long long.

Complexity

For each test case, the time complexity is and the auxiliary space complexity is .

C++17 Implementation

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n, a, b, x;
        cin >> n >> a >> b >> x;
        cout << max(n / a, n * x / b) << '\n';
    }
}