Розв'язок
Оскільки a\le b, до множення грошей достатньо купувати квитки лише в першому кінотеатрі: квиток у другий коштує не менше.
Нехай до множення ми купили квитків у перший кінотеатр. Тоді після множення залишиться (n-qa)x гривень, тому загальна кількість квитків дорівнюватиме
Якщо ax\ge b, то q\le qax/b, отже
Цього значення можна досягти, якщо одразу помножити всі гроші на і купувати квитки в другий кінотеатр.
Якщо ж ax\le b, то x/b\le1/a, звідки
Цього значення можна досягти, купуючи квитки лише в перший кінотеатр й не виконуючи множення.
Отже, незалежно від співвідношення та , відповідь дорівнює
Добуток може досягати 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';
}
}