Два кінотеатри#13120

Два кінотеатри (Розбір)

Розв'язок

Оскільки a\le b, до множення грошей достатньо купувати квитки лише в першому кінотеатрі: квиток у другий коштує не менше.

Нехай до множення ми купили квитків у перший кінотеатр. Тоді після множення залишиться (n-qa)x гривень, тому загальна кількість квитків дорівнюватиме

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

Якщо ax\ge b, то q\le qax/b, отже

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

Цього значення можна досягти, якщо одразу помножити всі гроші на і купувати квитки в другий кінотеатр.

Якщо ж ax\le b, то x/b\le1/a, звідки

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

Цього значення можна досягти, купуючи квитки лише в перший кінотеатр й не виконуючи множення.

Отже, незалежно від співвідношення та , відповідь дорівнює

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

Добуток може досягати 10^{18}, тому використовуємо long long.

Складність

Для одного набору даних часова складність , додаткова пам'ять .

Реалізація C++17

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