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
If ax\ge b, then q\le qax/b, hence
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
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
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';
}
}