MOVRES -Editorial

Question Link




Suppose that the width and height of the screen are W and H correspondingly. Since W:H = x:y, we have H=W*(x/y).
Similarly, the width and height of the film frame w and h are related as h=w*q/p.
Imagine that Abhishek stretches or constricts the frame until it fits the screen horizontally or vertically, whichever happens first.

There are three cases to consider:

  • The horizontal to vertical ratio of the screen is less
  • Equal
  • More than the corresponding ratio of the frame.

In the first case (x/y < p/q)

The stretching process ends when the frame reaches the same width as the screen. That is, the frame will enlarge in W/w times and its new width will be W. Thus, its new height is h*(W/w) = w*(p/q) * W/w = W*(q/p).
We are interested in the ratio of unoccupied portion of the screen to its full size, which is (screen height - frame height) / (screen height) = W*(y/x) - W*(q/p) / W*(x/y) = (yp-xq)/yp.

In the second case (x/y > p/q)

The process ends when the frame reaches the same height as the screen. Its height will become H and its width will become w*(H/h) = w * W*(q/p) / (w*(q/p) = W*(y/x) * p/q. The unoccupied portion of the screen’s horizontal is (W - W*y/x * p/q)/W = (xq-yp)/xq.

In the third case

The frame fills the screen entirely and the answer will be 0. All that’s left is to print the answer as an irreducible fraction. We need to find the greatest common divisor of its nominator and denominator for this. It can be done using Euclidean algorithm or just through trial division by every number from 1 to q. Since q is no more than a product of two numbers from the input and these numbers are constrained by 1000, we need to try at most million numbers in the worst case.

Author's Solution
signed main()
    int test_case;
        int a,b,c,d;
        int ansa,ansb;
        int p=__gcd(ansa,ansb);
1 Like