Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
The ratio is the only thing that matters, not the exact numbers. What happens if you divide both by \,mod's best friend: ?
If and where , then any integer screen with ratio must look like for some positive integer . No other shape sneaks in.
Now translate the "reduced size" condition into inequalities: So what is the largest integer that satisfies both?
The area is Since are fixed and positive, maximizing area is exactly the same as maximizing . No fancy optimization, no drama.
Compute
If , output 0 0; otherwise output
That’s it. Binary search is technically possible, but honestly it would be like using a chainsaw to butter toast.
The requested aspect ratio is . But ratios have redundancy: and are the same thing.
Let Then and are coprime.
Now here’s the key number-theory fact:
Any pair of integers with ratio must be of the form for some integer .
Why? Because with . So , and the only integer pairs with that reduced ratio are common multiples of .
That’s the whole problem cracked open.
We are only allowed to reduce the monitor, so the new dimensions must satisfy Substitute and : Therefore, So the largest possible valid multiplier is just
The area of the new screen is Since and are fixed positive constants, maximizing is exactly the same as maximizing .
So we don’t need binary search, DP, black magic, or a blood sacrifice to the gods of geometry. Just compute the maximum legal .
If then even the smallest positive screen with this ratio doesn’t fit, so the answer is
Otherwise the answer is simply
After reducing to coprime :
That’s a complete proof. Nice and clean.
We only compute one gcd and a few divisions: for the gcd, and otherwise.
Memory usage is
With constraints up to , long long is more than enough.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
ll a, b, x, y;
cin >> a >> b >> x >> y;
ll g = std::gcd(x, y);
x /= g;
y /= g;
ll k = min(a / x, b / y);
if (k == 0) {
cout << "0 0\n";
} else {
cout << k * x << ' ' << k * y << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
ll a, b, x, y;
cin >> a >> b >> x >> y;
ll g = std::gcd(x, y);
x /= g;
y /= g;
ll k = min(a / x, b / y);
if (k == 0) {
cout << "0 0\n";
} else {
cout << k * x << ' ' << k * y << '\n';
}
return 0;
}